/* * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README */ /* * Written by Anatoly P. Pinchuk [email protected] * Programm System Institute * Pereslavl-Zalessky Russia */ #include <linux/time.h> #include <linux/string.h> #include <linux/pagemap.h> #include <linux/bio.h> #include "reiserfs.h" #include <linux/buffer_head.h> #include <linux/quotaops.h> /* Does the buffer contain a disk block which is in the tree. */ inline int B_IS_IN_TREE(const struct buffer_head *bh) { … } /* to get item head in le form */ inline void copy_item_head(struct item_head *to, const struct item_head *from) { … } /* * k1 is pointer to on-disk structure which is stored in little-endian * form. k2 is pointer to cpu variable. For key of items of the same * object this returns 0. * Returns: -1 if key1 < key2 * 0 if key1 == key2 * 1 if key1 > key2 */ inline int comp_short_keys(const struct reiserfs_key *le_key, const struct cpu_key *cpu_key) { … } /* * k1 is pointer to on-disk structure which is stored in little-endian * form. k2 is pointer to cpu variable. * Compare keys using all 4 key fields. * Returns: -1 if key1 < key2 0 * if key1 = key2 1 if key1 > key2 */ static inline int comp_keys(const struct reiserfs_key *le_key, const struct cpu_key *cpu_key) { … } inline int comp_short_le_keys(const struct reiserfs_key *key1, const struct reiserfs_key *key2) { … } inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from) { … } /* * this does not say which one is bigger, it only returns 1 if keys * are not equal, 0 otherwise */ inline int comp_le_keys(const struct reiserfs_key *k1, const struct reiserfs_key *k2) { … } /************************************************************************** * Binary search toolkit function * * Search for an item in the array by the item key * * Returns: 1 if found, 0 if not found; * * *pos = number of the searched element if found, else the * * number of the first element that is larger than key. * **************************************************************************/ /* * For those not familiar with binary search: lbound is the leftmost item * that it could be, rbound the rightmost item that it could be. We examine * the item halfway between lbound and rbound, and that tells us either * that we can increase lbound, or decrease rbound, or that we have found it, * or if lbound <= rbound that there are no possible items, and we have not * found it. With each examination we cut the number of possible items it * could be by one more than half rounded down, or we find it. */ static inline int bin_search(const void *key, /* Key to search for. */ const void *base, /* First item in the array. */ int num, /* Number of items in the array. */ /* * Item size in the array. searched. Lest the * reader be confused, note that this is crafted * as a general function, and when it is applied * specifically to the array of item headers in a * node, width is actually the item header size * not the item size. */ int width, int *pos /* Number of the searched for element. */ ) { … } /* Minimal possible key. It is never in the tree. */ const struct reiserfs_key MIN_KEY = …; /* Maximal possible key. It is never in the tree. */ static const struct reiserfs_key MAX_KEY = …; /* * Get delimiting key of the buffer by looking for it in the buffers in the * path, starting from the bottom of the path, and going upwards. We must * check the path's validity at each step. If the key is not in the path, * there is no delimiting key in the tree (buffer is first or last buffer * in tree), and in this case we return a special key, either MIN_KEY or * MAX_KEY. */ static inline const struct reiserfs_key *get_lkey(const struct treepath *chk_path, const struct super_block *sb) { … } /* Get delimiting key of the buffer at the path and its right neighbor. */ inline const struct reiserfs_key *get_rkey(const struct treepath *chk_path, const struct super_block *sb) { … } /* * Check whether a key is contained in the tree rooted from a buffer at a path. * This works by looking at the left and right delimiting keys for the buffer * in the last path_element in the path. These delimiting keys are stored * at least one level above that buffer in the tree. If the buffer is the * first or last node in the tree order then one of the delimiting keys may * be absent, and in this case get_lkey and get_rkey return a special key * which is MIN_KEY or MAX_KEY. */ static inline int key_in_buffer( /* Path which should be checked. */ struct treepath *chk_path, /* Key which should be checked. */ const struct cpu_key *key, struct super_block *sb ) { … } int reiserfs_check_path(struct treepath *p) { … } /* * Drop the reference to each buffer in a path and restore * dirty bits clean when preparing the buffer for the log. * This version should only be called from fix_nodes() */ void pathrelse_and_restore(struct super_block *sb, struct treepath *search_path) { … } /* Drop the reference to each buffer in a path */ void pathrelse(struct treepath *search_path) { … } static int has_valid_deh_location(struct buffer_head *bh, struct item_head *ih) { … } static int is_leaf(char *buf, int blocksize, struct buffer_head *bh) { … } /* returns 1 if buf looks like an internal node, 0 otherwise */ static int is_internal(char *buf, int blocksize, struct buffer_head *bh) { … } /* * make sure that bh contains formatted node of reiserfs tree of * 'level'-th level */ static int is_tree_node(struct buffer_head *bh, int level) { … } #define SEARCH_BY_KEY_READA … /* * The function is NOT SCHEDULE-SAFE! * It might unlock the write lock if we needed to wait for a block * to be read. Note that in this case it won't recover the lock to avoid * high contention resulting from too much lock requests, especially * the caller (search_by_key) will perform other schedule-unsafe * operations just after calling this function. * * @return depth of lock to be restored after read completes */ static int search_by_key_reada(struct super_block *s, struct buffer_head **bh, b_blocknr_t *b, int num) { … } /* * This function fills up the path from the root to the leaf as it * descends the tree looking for the key. It uses reiserfs_bread to * try to find buffers in the cache given their block number. If it * does not find them in the cache it reads them from disk. For each * node search_by_key finds using reiserfs_bread it then uses * bin_search to look through that node. bin_search will find the * position of the block_number of the next node if it is looking * through an internal node. If it is looking through a leaf node * bin_search will find the position of the item which has key either * equal to given key, or which is the maximal key less than the given * key. search_by_key returns a path that must be checked for the * correctness of the top of the path but need not be checked for the * correctness of the bottom of the path */ /* * search_by_key - search for key (and item) in stree * @sb: superblock * @key: pointer to key to search for * @search_path: Allocated and initialized struct treepath; Returned filled * on success. * @stop_level: How far down the tree to search, Use DISK_LEAF_NODE_LEVEL to * stop at leaf level. * * The function is NOT SCHEDULE-SAFE! */ int search_by_key(struct super_block *sb, const struct cpu_key *key, struct treepath *search_path, int stop_level) { … } /* * Form the path to an item and position in this item which contains * file byte defined by key. If there is no such item * corresponding to the key, we point the path to the item with * maximal key less than key, and *pos_in_item is set to one * past the last entry/byte in the item. If searching for entry in a * directory item, and it is not found, *pos_in_item is set to one * entry more than the entry with maximal key which is less than the * sought key. * * Note that if there is no entry in this same node which is one more, * then we point to an imaginary entry. for direct items, the * position is in units of bytes, for indirect items the position is * in units of blocknr entries, for directory items the position is in * units of directory entries. */ /* The function is NOT SCHEDULE-SAFE! */ int search_for_position_by_key(struct super_block *sb, /* Key to search (cpu variable) */ const struct cpu_key *p_cpu_key, /* Filled up by this function. */ struct treepath *search_path) { … } /* Compare given item and item pointed to by the path. */ int comp_items(const struct item_head *stored_ih, const struct treepath *path) { … } /* prepare for delete or cut of direct item */ static inline int prepare_for_direct_item(struct treepath *path, struct item_head *le_ih, struct inode *inode, loff_t new_file_length, int *cut_size) { … } static inline int prepare_for_direntry_item(struct treepath *path, struct item_head *le_ih, struct inode *inode, loff_t new_file_length, int *cut_size) { … } #define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD … /* * If the path points to a directory or direct item, calculate mode * and the size cut, for balance. * If the path points to an indirect item, remove some number of its * unformatted nodes. * In case of file truncate calculate whether this item must be * deleted/truncated or last unformatted node of this item will be * converted to a direct item. * This function returns a determination of what balance mode the * calling function should employ. */ static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, struct inode *inode, struct treepath *path, const struct cpu_key *item_key, /* * Number of unformatted nodes * which were removed from end * of the file. */ int *removed, int *cut_size, /* MAX_KEY_OFFSET in case of delete. */ unsigned long long new_file_length ) { … } /* Calculate number of bytes which will be deleted or cut during balance */ static int calc_deleted_bytes_number(struct tree_balance *tb, char mode) { … } static void init_tb_struct(struct reiserfs_transaction_handle *th, struct tree_balance *tb, struct super_block *sb, struct treepath *path, int size) { … } void padd_item(char *item, int total_length, int length) { … } #ifdef REISERQUOTA_DEBUG char key2type(struct reiserfs_key *ih) { if (is_direntry_le_key(2, ih)) return 'd'; if (is_direct_le_key(2, ih)) return 'D'; if (is_indirect_le_key(2, ih)) return 'i'; if (is_statdata_le_key(2, ih)) return 's'; return 'u'; } char head2type(struct item_head *ih) { if (is_direntry_le_ih(ih)) return 'd'; if (is_direct_le_ih(ih)) return 'D'; if (is_indirect_le_ih(ih)) return 'i'; if (is_statdata_le_ih(ih)) return 's'; return 'u'; } #endif /* * Delete object item. * th - active transaction handle * path - path to the deleted item * item_key - key to search for the deleted item * indode - used for updating i_blocks and quotas * un_bh - NULL or unformatted node pointer */ int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *path, const struct cpu_key *item_key, struct inode *inode, struct buffer_head *un_bh) { … } /* * Summary Of Mechanisms For Handling Collisions Between Processes: * * deletion of the body of the object is performed by iput(), with the * result that if multiple processes are operating on a file, the * deletion of the body of the file is deferred until the last process * that has an open inode performs its iput(). * * writes and truncates are protected from collisions by use of * semaphores. * * creates, linking, and mknod are protected from collisions with other * processes by making the reiserfs_add_entry() the last step in the * creation, and then rolling back all changes if there was a collision. * - Hans */ /* this deletes item which never gets split */ void reiserfs_delete_solid_item(struct reiserfs_transaction_handle *th, struct inode *inode, struct reiserfs_key *key) { … } int reiserfs_delete_object(struct reiserfs_transaction_handle *th, struct inode *inode) { … } static void unmap_buffers(struct page *page, loff_t pos) { … } static int maybe_indirect_to_direct(struct reiserfs_transaction_handle *th, struct inode *inode, struct page *page, struct treepath *path, const struct cpu_key *item_key, loff_t new_file_size, char *mode) { … } /* * we did indirect_to_direct conversion. And we have inserted direct * item successesfully, but there were no disk space to cut unfm * pointer being converted. Therefore we have to delete inserted * direct item(s) */ static void indirect_to_direct_roll_back(struct reiserfs_transaction_handle *th, struct inode *inode, struct treepath *path) { … } /* (Truncate or cut entry) or delete object item. Returns < 0 on failure */ int reiserfs_cut_from_item(struct reiserfs_transaction_handle *th, struct treepath *path, struct cpu_key *item_key, struct inode *inode, struct page *page, loff_t new_file_size) { … } static void truncate_directory(struct reiserfs_transaction_handle *th, struct inode *inode) { … } /* * Truncate file to the new size. Note, this must be called with a * transaction already started */ int reiserfs_do_truncate(struct reiserfs_transaction_handle *th, struct inode *inode, /* ->i_size contains new size */ struct page *page, /* up to date for last block */ /* * when it is called by file_release to convert * the tail - no timestamps should be updated */ int update_timestamps ) { … } #ifdef CONFIG_REISERFS_CHECK /* this makes sure, that we __append__, not overwrite or add holes */ static void check_research_for_paste(struct treepath *path, const struct cpu_key *key) { … } #endif /* config reiserfs check */ /* * Paste bytes to the existing item. * Returns bytes number pasted into the item. */ int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th, /* Path to the pasted item. */ struct treepath *search_path, /* Key to search for the needed item. */ const struct cpu_key *key, /* Inode item belongs to */ struct inode *inode, /* Pointer to the bytes to paste. */ const char *body, /* Size of pasted bytes. */ int pasted_size) { … } /* * Insert new item into the buffer at the path. * th - active transaction handle * path - path to the inserted item * ih - pointer to the item header to insert * body - pointer to the bytes to insert */ int reiserfs_insert_item(struct reiserfs_transaction_handle *th, struct treepath *path, const struct cpu_key *key, struct item_head *ih, struct inode *inode, const char *body) { … }
Codebase Browser
linux