// SPDX-License-Identifier: GPL-2.0-only /* * Copyright (C) Sistina Software, Inc. 1997-2003 All rights reserved. * Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved. */ /* * Implements Extendible Hashing as described in: * "Extendible Hashing" by Fagin, et al in * __ACM Trans. on Database Systems__, Sept 1979. * * * Here's the layout of dirents which is essentially the same as that of ext2 * within a single block. The field de_name_len is the number of bytes * actually required for the name (no null terminator). The field de_rec_len * is the number of bytes allocated to the dirent. The offset of the next * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is * deleted, the preceding dirent inherits its allocated space, ie * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained * by adding de_rec_len to the current dirent, this essentially causes the * deleted dirent to get jumped over when iterating through all the dirents. * * When deleting the first dirent in a block, there is no previous dirent so * the field de_ino is set to zero to designate it as deleted. When allocating * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the * first dirent has (de_ino == 0) and de_rec_len is large enough, this first * dirent is allocated. Otherwise it must go through all the 'used' dirents * searching for one in which the amount of total space minus the amount of * used space will provide enough space for the new dirent. * * There are two types of blocks in which dirents reside. In a stuffed dinode, * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of * the block. In leaves, they begin at offset sizeof(struct gfs2_leaf) from the * beginning of the leaf block. The dirents reside in leaves when * * dip->i_diskflags & GFS2_DIF_EXHASH is true * * Otherwise, the dirents are "linear", within a single stuffed dinode block. * * When the dirents are in leaves, the actual contents of the directory file are * used as an array of 64-bit block pointers pointing to the leaf blocks. The * dirents are NOT in the directory file itself. There can be more than one * block pointer in the array that points to the same leaf. In fact, when a * directory is first converted from linear to exhash, all of the pointers * point to the same leaf. * * When a leaf is completely full, the size of the hash table can be * doubled unless it is already at the maximum size which is hard coded into * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list, * but never before the maximum hash table size has been reached. */ #define pr_fmt(fmt) … #include <linux/slab.h> #include <linux/spinlock.h> #include <linux/buffer_head.h> #include <linux/sort.h> #include <linux/gfs2_ondisk.h> #include <linux/crc32.h> #include <linux/vmalloc.h> #include <linux/bio.h> #include "gfs2.h" #include "incore.h" #include "dir.h" #include "glock.h" #include "inode.h" #include "meta_io.h" #include "quota.h" #include "rgrp.h" #include "trans.h" #include "bmap.h" #include "util.h" #define MAX_RA_BLOCKS … #define gfs2_disk_hash2offset(h) … #define gfs2_dir_offset2hash(p) … #define GFS2_HASH_INDEX_MASK … #define GFS2_USE_HASH_FLAG … struct qstr gfs2_qdot __read_mostly; struct qstr gfs2_qdotdot __read_mostly; gfs2_dscan_t; int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block, struct buffer_head **bhp) { … } static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block, struct buffer_head **bhp) { … } static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf, unsigned int offset, unsigned int size) { … } /** * gfs2_dir_write_data - Write directory information to the inode * @ip: The GFS2 inode * @buf: The buffer containing information to be written * @offset: The file offset to start writing at * @size: The amount of data to write * * Returns: The number of bytes correctly written or error code */ static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf, u64 offset, unsigned int size) { … } static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, __be64 *buf, unsigned int size) { … } /** * gfs2_dir_read_data - Read a data from a directory inode * @ip: The GFS2 Inode * @buf: The buffer to place result into * @size: Amount of data to transfer * * Returns: The amount of data actually copied or the error */ static int gfs2_dir_read_data(struct gfs2_inode *ip, __be64 *buf, unsigned int size) { … } /** * gfs2_dir_get_hash_table - Get pointer to the dir hash table * @ip: The inode in question * * Returns: The hash table or an error */ static __be64 *gfs2_dir_get_hash_table(struct gfs2_inode *ip) { … } /** * gfs2_dir_hash_inval - Invalidate dir hash * @ip: The directory inode * * Must be called with an exclusive glock, or during glock invalidation. */ void gfs2_dir_hash_inval(struct gfs2_inode *ip) { … } static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent) { … } static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent, const struct qstr *name, int ret) { … } static int gfs2_dirent_find(const struct gfs2_dirent *dent, const struct qstr *name, void *opaque) { … } static int gfs2_dirent_prev(const struct gfs2_dirent *dent, const struct qstr *name, void *opaque) { … } /* * name->name holds ptr to start of block. * name->len holds size of block. */ static int gfs2_dirent_last(const struct gfs2_dirent *dent, const struct qstr *name, void *opaque) { … } /* Look for the dirent that contains the offset specified in data. Once we * find that dirent, there must be space available there for the new dirent */ static int gfs2_dirent_find_offset(const struct gfs2_dirent *dent, const struct qstr *name, void *ptr) { … } static int gfs2_dirent_find_space(const struct gfs2_dirent *dent, const struct qstr *name, void *opaque) { … } struct dirent_gather { … }; static int gfs2_dirent_gather(const struct gfs2_dirent *dent, const struct qstr *name, void *opaque) { … } /* * Other possible things to check: * - Inode located within filesystem size (and on valid block) * - Valid directory entry type * Not sure how heavy-weight we want to make this... could also check * hash is correct for example, but that would take a lot of extra time. * For now the most important thing is to check that the various sizes * are correct. */ static int gfs2_check_dirent(struct gfs2_sbd *sdp, struct gfs2_dirent *dent, unsigned int offset, unsigned int size, unsigned int len, int first) { … } static int gfs2_dirent_offset(struct gfs2_sbd *sdp, const void *buf) { … } static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf, unsigned int len, gfs2_dscan_t scan, const struct qstr *name, void *opaque) { … } static int dirent_check_reclen(struct gfs2_inode *dip, const struct gfs2_dirent *d, const void *end_p) { … } /** * dirent_next - Next dirent * @dip: the directory * @bh: The buffer * @dent: Pointer to list of dirents * * Returns: 0 on success, error code otherwise */ static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh, struct gfs2_dirent **dent) { … } /** * dirent_del - Delete a dirent * @dip: The GFS2 inode * @bh: The buffer * @prev: The previous dirent * @cur: The current dirent * */ static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh, struct gfs2_dirent *prev, struct gfs2_dirent *cur) { … } static struct gfs2_dirent *do_init_dirent(struct inode *inode, struct gfs2_dirent *dent, const struct qstr *name, struct buffer_head *bh, unsigned offset) { … } /* * Takes a dent from which to grab space as an argument. Returns the * newly created dent. */ static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode, struct gfs2_dirent *dent, const struct qstr *name, struct buffer_head *bh) { … } static struct gfs2_dirent *gfs2_dirent_split_alloc(struct inode *inode, struct buffer_head *bh, const struct qstr *name, void *ptr) { … } static int get_leaf(struct gfs2_inode *dip, u64 leaf_no, struct buffer_head **bhp) { … } /** * get_leaf_nr - Get a leaf number associated with the index * @dip: The GFS2 inode * @index: hash table index of the targeted leaf * @leaf_out: Resulting leaf block number * * Returns: 0 on success, error code otherwise */ static int get_leaf_nr(struct gfs2_inode *dip, u32 index, u64 *leaf_out) { … } static int get_first_leaf(struct gfs2_inode *dip, u32 index, struct buffer_head **bh_out) { … } static struct gfs2_dirent *gfs2_dirent_search(struct inode *inode, const struct qstr *name, gfs2_dscan_t scan, struct buffer_head **pbh) { … } static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth) { … } /** * dir_make_exhash - Convert a stuffed directory into an ExHash directory * @inode: The directory inode to be converted to exhash * * Returns: 0 on success, error code otherwise */ static int dir_make_exhash(struct inode *inode) { … } /** * dir_split_leaf - Split a leaf block into two * @inode: The directory inode to be split * @name: name of the dirent we're trying to insert * * Returns: 0 on success, error code on failure */ static int dir_split_leaf(struct inode *inode, const struct qstr *name) { … } /** * dir_double_exhash - Double size of ExHash table * @dip: The GFS2 dinode * * Returns: 0 on success, error code on failure */ static int dir_double_exhash(struct gfs2_inode *dip) { … } /** * compare_dents - compare directory entries by hash value * @a: first dent * @b: second dent * * When comparing the hash entries of @a to @b: * gt: returns 1 * lt: returns -1 * eq: returns 0 */ static int compare_dents(const void *a, const void *b) { … } /** * do_filldir_main - read out directory entries * @dip: The GFS2 inode * @ctx: what to feed the entries to * @darr: an array of struct gfs2_dirent pointers to read * @entries: the number of entries in darr * @sort_start: index of the directory array to start our sort * @copied: pointer to int that's non-zero if a entry has been copied out * * Jump through some hoops to make sure that if there are hash collsions, * they are read out at the beginning of a buffer. We want to minimize * the possibility that they will fall into different readdir buffers or * that someone will want to seek to that location. * * Returns: errno, >0 if the actor tells you to stop */ static int do_filldir_main(struct gfs2_inode *dip, struct dir_context *ctx, struct gfs2_dirent **darr, u32 entries, u32 sort_start, int *copied) { … } static void *gfs2_alloc_sort_buffer(unsigned size) { … } static int gfs2_set_cookies(struct gfs2_sbd *sdp, struct buffer_head *bh, unsigned leaf_nr, struct gfs2_dirent **darr, unsigned entries) { … } static int gfs2_dir_read_leaf(struct inode *inode, struct dir_context *ctx, int *copied, unsigned *depth, u64 leaf_no) { … } /** * gfs2_dir_readahead - Issue read-ahead requests for leaf blocks. * @inode: the directory inode * @hsize: hash table size * @index: index into the hash table * @f_ra: read-ahead parameters * * Note: we can't calculate each index like dir_e_read can because we don't * have the leaf, and therefore we don't have the depth, and therefore we * don't have the length. So we have to just read enough ahead to make up * for the loss of information. */ static void gfs2_dir_readahead(struct inode *inode, unsigned hsize, u32 index, struct file_ra_state *f_ra) { … } /** * dir_e_read - Reads the entries from a directory into a filldir buffer * @inode: the directory inode * @ctx: actor to feed the entries to * @f_ra: read-ahead parameters * * Returns: errno */ static int dir_e_read(struct inode *inode, struct dir_context *ctx, struct file_ra_state *f_ra) { … } int gfs2_dir_read(struct inode *inode, struct dir_context *ctx, struct file_ra_state *f_ra) { … } /** * gfs2_dir_search - Search a directory * @dir: The GFS2 directory inode * @name: The name we are looking up * @fail_on_exist: Fail if the name exists rather than looking it up * * This routine searches a directory for a file or another directory. * Assumes a glock is held on dip. * * Returns: errno */ struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name, bool fail_on_exist) { … } int gfs2_dir_check(struct inode *dir, const struct qstr *name, const struct gfs2_inode *ip) { … } /** * dir_new_leaf - Add a new leaf onto hash chain * @inode: The directory * @name: The name we are adding * * This adds a new dir leaf onto an existing leaf when there is not * enough space to add a new dir entry. This is a last resort after * we've expanded the hash table to max size and also split existing * leaf blocks, so it will only occur for very large directories. * * The dist parameter is set to 1 for leaf blocks directly attached * to the hash table, 2 for one layer of indirection, 3 for two layers * etc. We are thus able to tell the difference between an old leaf * with dist set to zero (i.e. "don't know") and a new one where we * set this information for debug/fsck purposes. * * Returns: 0 on success, or -ve on error */ static int dir_new_leaf(struct inode *inode, const struct qstr *name) { … } static u16 gfs2_inode_ra_len(const struct gfs2_inode *ip) { … } /** * gfs2_dir_add - Add new filename into directory * @inode: The directory inode * @name: The new name * @nip: The GFS2 inode to be linked in to the directory * @da: The directory addition info * * If the call to gfs2_diradd_alloc_required resulted in there being * no need to allocate any new directory blocks, then it will contain * a pointer to the directory entry and the bh in which it resides. We * can use that without having to repeat the search. If there was no * free space, then we must now create more space. * * Returns: 0 on success, error code on failure */ int gfs2_dir_add(struct inode *inode, const struct qstr *name, const struct gfs2_inode *nip, struct gfs2_diradd *da) { … } /** * gfs2_dir_del - Delete a directory entry * @dip: The GFS2 inode * @dentry: The directory entry we want to delete * * Returns: 0 on success, error code on failure */ int gfs2_dir_del(struct gfs2_inode *dip, const struct dentry *dentry) { … } /** * gfs2_dir_mvino - Change inode number of directory entry * @dip: The GFS2 directory inode * @filename: the filename to be moved * @nip: the new GFS2 inode * @new_type: the de_type of the new dirent * * This routine changes the inode number of a directory entry. It's used * by rename to change ".." when a directory is moved. * Assumes a glock is held on dvp. * * Returns: errno */ int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename, const struct gfs2_inode *nip, unsigned int new_type) { … } /** * leaf_dealloc - Deallocate a directory leaf * @dip: the directory * @index: the hash table offset in the directory * @len: the number of pointers to this leaf * @leaf_no: the leaf number * @leaf_bh: buffer_head for the starting leaf * @last_dealloc: 1 if this is the final dealloc for the leaf, else 0 * * Returns: errno */ static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len, u64 leaf_no, struct buffer_head *leaf_bh, int last_dealloc) { … } /** * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory * @dip: the directory * * Dealloc all on-disk directory leaves to FREEMETA state * Change on-disk inode type to "regular file" * * Returns: errno */ int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip) { … } /** * gfs2_diradd_alloc_required - find if adding entry will require an allocation * @inode: the directory inode being written to * @name: the filename that's going to be added * @da: The structure to return dir alloc info * * Returns: 0 if ok, -ve on error */ int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name, struct gfs2_diradd *da) { … }
Codebase Browser
linux