[Libsysio-commit] HEAD: libsysio/src inode.c
Brought to you by:
lward
Menu
▾
▴
[Libsysio-commit] HEAD: libsysio/src inode.c
|
From: Lee W. <lw...@us...> - 2008-07-26 01:31:44
|
Update of /cvsroot/libsysio/libsysio/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv8078 Modified Files: inode.c Log Message: The file system record now maintains the list of associated i-nodes as a tree. This speeds up _sysio_i_find greatly when the names table cache is allowed to become large. Removed deprecated function named _sysio_prune Index: inode.c =================================================================== RCS file: /cvsroot/libsysio/libsysio/src/inode.c,v retrieving revision 1.45 retrieving revision 1.46 diff -u -w -b -B -p -r1.45 -r1.46 --- inode.c 14 Jul 2008 19:15:00 -0000 1.45 +++ inode.c 26 Jul 2008 01:31:40 -0000 1.46 @@ -68,6 +67,10 @@ #ifndef NAMES_TABLE_LEN #define NAMES_TABLE_LEN 251 #endif +/* + * Desired high-water mark. + */ +#define P_RECLAIM_MIN 16 /* * Active i-nodes in the system and the number of same. @@ -79,11 +82,6 @@ static size_t n_inodes = 0; * Number of names tracked by the system. */ static size_t n_names = 0; -/* - * Desired number of base path nodes to maintain. - */ -static size_t desired_names = (3 * NAMES_TABLE_LEN); -static size_t max_names; /* * List of all path-nodes (aliases) that are not currently referenced. @@ -103,6 +101,9 @@ struct pnode *_sysio_root = NULL; static struct { unsigned long long cst_iprobes; unsigned long long cst_ihits; + unsigned long long cst_ireclaims; + unsigned long long cst_iexamined; + unsigned long long cst_idismissed; unsigned long long cst_pbprobes; unsigned long long cst_pbhits; unsigned long long cst_preclaims; @@ -115,6 +116,9 @@ ino_cstats_init() { cstats.cst_iprobes = cstats.cst_ihits = 0; + cstats.cst_ireclaims = + cstats.cst_iexamined = + cstats.cst_idismissed = 0; cstats.cst_pbprobes = cstats.cst_pbhits = 0; cstats.cst_preclaims = cstats.cst_pexamined = @@ -142,8 +146,6 @@ _sysio_i_init() TAILQ_INIT(&_sysio_idle_pnodes); - max_names = desired_names; - #ifdef INO_CACHE_STATS ino_cstats_init(); #endif @@ -160,34 +162,88 @@ i_reclaim() struct inode *next, *ino; size_t t; - t = n_inodes / 2; + INO_CST_UPDCNT(ireclaims); + t = n_inodes - n_inodes / 10; next = _sysio_inodes.tqh_first; while (next) { ino = next; next = ino->i_nodes.tqe_next; + INO_CST_UPDCNT(iexamined); if (ino->i_ref || ino->i_immune) continue; + INO_CST_UPDCNT(idismissed); _sysio_i_gone(ino); if (n_inodes < t) break; } } -static unsigned -hash(struct file_identifier *fid) +/* + * Compare two file identifiers, returning -1 if length of first is + * less than the second, or 1 if length of first greater than then the + * second, or the result of a memory compare if lengths are the same. + */ +static int +compar_fid(const struct file_identifier *fid1, + const struct file_identifier *fid2) { - size_t n; - unsigned char *ucp; - unsigned hkey; - n = fid->fid_len; - ucp = fid->fid_data; - hkey = 0; - do { - hkey <<= 1; - hkey += *ucp++; - } while (--n); - return hkey; + if (fid1->fid_len < fid2->fid_len) + return -1; + if (fid1->fid_len > fid2->fid_len) + return 1; + return memcmp(fid1->fid_data, fid2->fid_data, fid1->fid_len); +} + +/* + * Insert inode into per-fs inode cache. + * + * NB: The given inode must not already be in the cache. + */ +static void +icache_insert(struct inode *ino) +{ + + if (_sysio_tree_search(&ino->i_tnode, + &ino->i_fs->fs_icache, + (int (*)(const void *, + const void *))compar_fid) != + &ino->i_tnode) + abort(); +} + +/* + * Remove inode from inode cache. + * + * NB: The inode must be present in the cache. + */ +static void +icache_delete(struct inode *ino) +{ + + if (_sysio_tree_delete(ino->i_fid, + &ino->i_fs->fs_icache, + (int (*)(const void *, + const void *))compar_fid) != + &ino->i_tnode) + abort(); +} + +/* + * Find, and return, inode with given file identifier. If not found, NULL is + * returned instead. + */ +static struct inode * +icache_lookup(struct filesys *fs, struct file_identifier *fid) +{ + struct tree_node *tn; + + tn = + _sysio_tree_find(fid, + &fs->fs_icache, + (int (*)(const void *, + const void *))compar_fid); + return tn ? TREE_ENTRY(tn, inode, i_tnode) : NULL; } /* @@ -206,7 +262,6 @@ _sysio_i_new(struct filesys *fs, { struct inode *ino; struct inode_ops operations; - struct itable_entry *head; if (n_inodes > n_names) { /* @@ -244,10 +299,9 @@ _sysio_i_new(struct filesys *fs, I_INIT(ino, fs, stat, &operations, fid, immunity, private); ino->i_ref = 1; TAILQ_INSERT_TAIL(&_sysio_inodes, ino, i_nodes); - head = &fs->fs_itbl[hash(fid) % FS_ITBLSIZ]; - LIST_INSERT_HEAD(head, ino, i_link); I_GET(ino); + icache_insert(ino); I_RELE(ino); n_inodes++; @@ -264,23 +318,13 @@ struct inode * _sysio_i_find(struct filesys *fs, struct file_identifier *fid) { struct inode *ino; - struct itable_entry *head; - head = &fs->fs_itbl[hash(fid) % FS_ITBLSIZ]; - /* - * Look for existing. - */ - for (ino = head->lh_first; ino; ino = ino->i_link.le_next) - if (ino->i_fid->fid_len == fid->fid_len && - memcmp(ino->i_fid->fid_data, - fid->fid_data, - fid->fid_len) == 0) { + INO_CST_UPDCNT(iprobes); + ino = icache_lookup(fs, fid); + if (!ino) + return NULL; I_GET(ino); INO_CST_UPDCNT(ihits); - break; - } - - INO_CST_UPDCNT(iprobes); return ino; } @@ -294,7 +338,7 @@ _sysio_i_gone(struct inode *ino) if (ino->i_ref) abort(); if (!ino->i_zombie) - LIST_REMOVE(ino, i_link); + icache_delete(ino); TAILQ_REMOVE(&_sysio_inodes, ino, i_nodes); (*ino->i_ops.inop_gone)(ino); I_UNLOCK(ino); @@ -314,8 +358,8 @@ _sysio_i_undead(struct inode *ino) if (ino->i_zombie) return; - LIST_REMOVE(ino, i_link); ino->i_zombie = 1; + icache_delete(ino); } #ifdef P_RECLAIM_DEBUG @@ -349,17 +393,11 @@ p_reclaim_debug() * Garbage collect idle path (and base path) nodes tracked by the system. */ static void -p_reclaim(unsigned count) +p_reclaim(unsigned limit) { - int adjust; struct pnode *next, *pno; - size_t t; struct pnode_base *pb; - adjust = 0; - if (count) - adjust = 1; - #ifdef P_RECLAIM_DEBUG p_reclaim_debug(); #endif @@ -368,7 +406,6 @@ p_reclaim(unsigned count) next = _sysio_idle_pnodes.tqh_first; if (!next) return; - t = n_names / 2; do { INO_CST_UPDCNT(pexamined); pno = next; @@ -400,18 +437,7 @@ p_reclaim(unsigned count) _sysio_pb_gone(pb); else PB_UNLOCK(pb); - } while ((!count || --count) && n_names > t && next); - - if (!adjust) - return; - - if (n_names > t) - max_names += t; - else { - max_names = t; - if (max_names < desired_names) - max_names = desired_names; - } + } while ((!limit || limit-- > 1) && next); } static int @@ -498,13 +524,6 @@ _sysio_pb_new(struct qstr *name, struct struct pnode_base *pb; static struct qstr noname = { NULL, 0, 0 }; - if (n_names > max_names) { - /* - * Try to limit growth. - */ - p_reclaim(0); - } - pb = malloc(sizeof(struct pnode_base) + name->len); if (!pb) return NULL; @@ -532,12 +551,23 @@ _sysio_pb_new(struct qstr *name, struct ncache_insert(pb); } + n_names++; + assert(n_names); + #ifdef P_RECLAIM_DEBUG LIST_INSERT_HEAD(&pbnodes, pb, pb_links); #endif - n_names++; - assert(n_names); + if (n_names > NAMES_TABLE_LEN) { + unsigned n; + /* + * Limit growth. + */ + n = n_names - NAMES_TABLE_LEN; + if (n < P_RECLAIM_MIN) + n = P_RECLAIM_MIN; + p_reclaim(n); + } return pb; } @@ -609,6 +639,10 @@ _sysio_i_shutdown() _sysio_cprintf("inode: probe %llu, hit %llu\n", cstats.cst_iprobes, cstats.cst_ihits); + _sysio_cprintf("inode: reclaims %llu, examined %llu dismissed %llu\n", + cstats.cst_ireclaims, + cstats.cst_iexamined, + cstats.cst_idismissed); _sysio_cprintf("pbnode: probe %llu, hit %llu\n", cstats.cst_pbprobes, cstats.cst_pbhits); @@ -617,7 +651,6 @@ _sysio_i_shutdown() cstats.cst_pexamined, cstats.cst_pdismissed); #endif - max_names = desired_names; return; } @@ -971,32 +1004,6 @@ _sysio_p_find_alias(struct pnode *parent return err; } -#if 0 -/* - * Prune idle path base nodes from the passed sub-tree, including the root. - */ -static void -_sysio_prune(struct pnode_base *rpb) -{ - struct pnode_base *nxtpb, *pb; - - nxtpb = rpb->pb_children.lh_first; - while ((pb = nxtpb)) { - nxtpb = pb->pb_sibs.le_next; - if (pb->pb_aliases.lh_first) - continue; - if (pb->pb_children.lh_first) { - _sysio_prune(pb); - continue; - } - _sysio_pb_gone(pb); - } - if (rpb->pb_children.lh_first) - return; - _sysio_pb_gone(rpb); -} -#endif - static size_t p_remove_aliases(struct mount *mnt, struct pnode_base *pb) { |
