From dea30123ebc0c5f6a1c10ced3d172e2be2141690 Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Sun, 20 Mar 2011 20:12:35 +1100 Subject: [PATCH] Add 'ls' command and directory searching. Also 'lafs_find_next' to find next allocated block. Signed-off-by: NeilBrown --- include/lafs/lafs.h | 24 + lib/dir-avl.c | 1072 ++++++++++++++++++++++++++++++++++++++++++ lib/internal.h | 44 ++ lib/lafs_dir_next.c | 53 +++ lib/lafs_find_dblk.c | 37 +- lib/lafs_find_next.c | 78 +++ lib/lafs_leaf_find.c | 112 +++++ tools/lafs.c | 46 ++ 8 files changed, 1445 insertions(+), 21 deletions(-) create mode 100644 lib/dir-avl.c create mode 100644 lib/lafs_dir_next.c create mode 100644 lib/lafs_find_next.c create mode 100644 lib/lafs_leaf_find.c diff --git a/include/lafs/lafs.h b/include/lafs/lafs.h index 4e777dd..6e5f3c5 100644 --- a/include/lafs/lafs.h +++ b/include/lafs/lafs.h @@ -10,6 +10,7 @@ #include #include +#define LAFS_NOBLOCK 0xFFFFFFFFUL struct lafs *lafs_alloc(void); int lafs_new(struct lafs *, int block_bytes); @@ -71,6 +72,29 @@ char *lafs_mount(struct lafs *fs, int force); void lafs_print_state(struct lafs_state *state, int size); void lafs_print_lafs(struct lafs *fs); void lafs_print_inode(struct lafs_ino *ino); +u32 lafs_find_next(struct lafs_ino *ino, u32 bnum); +int lafs_hash_name(u32 seed, int len, const char *name); +void lafs_dir_init_block(char *block, int psz, const char *name, int len, + u32 target, int type, int chain_offset); +int lafs_dir_add_ent(char *block, int psz, const char *name, int len, + u32 target, int type, u32 seed, u32 hash, int hashoffset); +int lafs_dir_del_ent(char *block, int psz, u32 seed, u32 hash); +void lafs_dir_split(char *orig, int psz, char *new1, char *new2, + const char *name, u32 target, int type, u32 *newhash, + u32 seed, u32 hash, int chainoffset); +void lafs_dir_repack(char *block, int psz, char *new, u32 seed, int merge); +int lafs_dir_find(char *block, int psz, u32 seed, u32 hash, u8 *pp); +int lafs_dir_empty(char *block); +int lafs_dir_blk_size(char *block, int psz); +int lafs_dir_next(struct lafs_ino *dir, u32 *indexp, char *name, + u32 *inop, int *typep); +uint64_t lafs_leaf_lookup(unsigned char *buf, int len, u32 startaddr, + u32 target, u32 *nextp); +struct lafs_iblk *lafs_leaf_find(struct lafs_ino *inode, + u32 addr, int adopt, u32 *next); + + + static inline struct lafs_dblk *dblk(struct lafs_blk *b) { diff --git a/lib/dir-avl.c b/lib/dir-avl.c new file mode 100644 index 0000000..a1b1076 --- /dev/null +++ b/lib/dir-avl.c @@ -0,0 +1,1072 @@ +/* + * fs/lafs/dir-avl.c + * Copyright (C) 2005-2009 + * Neil Brown + * Released under the GPL, version 2 + * + * A directory block is stored as an AVL tree. + * Entries are added to the end, and merged into + * the AVL tree. + * Deleted entries are left in place, but marked + * as deleted (pointer is 0) + * When a block becomes full, we re-pack it, + * or split it. + * + */ +#include +#include +#include "internal.h" + +/* TEA_transform borrowed from ext3 */ +#define DELTA 0x9E3779B9 + +static void TEA_transform(u32 buf[2], u32 const in[4]) +{ + u32 sum = 0; + u32 b0 = buf[0], b1 = buf[1]; + u32 a = in[0], b = in[1], c = in[2], d = in[3]; + int n = 16; + + do { + sum += DELTA; + b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); + b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); + } while (--n); + + buf[0] += b0; + buf[1] += b1; +} + +static void str2msg(u32 *msg, int len, const char *name) +{ + int i; + u32 part = 0; + int pad = len; + + if (len > 16) + len = 16; + for (i = 0; i < len ; i++) { + part = (part << 8) + name[i]; + if ((i%4) == 3) + *msg++ = part; + } + for ( ; i < 16 ; i++) { + part = (part<<8) + pad; + if ((i%4) == 3) + *msg++ = part; + } +} + +int lafs_hash_name(u32 seed, int len, const char *name) +{ + u32 buf[2]; + u32 msg[4]; + buf[0] = seed; + buf[1] = ~seed; + + switch (seed & 0x7) { + default: + return 0; + case 0: + return 1; + case 1: + while (len > 0) { + str2msg(msg, len, name); + TEA_transform(buf, msg); + len -= 16; + name += 16; + } + return buf[0] & 0x7fffffff; + } +} + +static u32 hash_piece(u32 seed, struct dirpiece *dp, u32 *offsetp) +{ + u32 hash = lafs_hash_name(seed, dp->length, dp->name); + u32 offset = 0; + switch (dp->chain_info) { + case 0: + break; + case 1: + offset = 1; + break; + case 2: + offset = (unsigned char) dp->name[dp->length]; + break; + case 3: + memcpy(&offset, dp->name + dp->length, 4); + offset = le32_to_cpu(offset); + break; + } + if (offsetp) + *offsetp = offset; + return hash + offset; +} + +/* dpaddr assumes that 'psz' (piece size) is valid when called */ +#define dpaddr(_block, _piece) ((struct dirpiece *)((_block) + ((_piece)<name, name, len); + + if (chain_offset <= 1) + dp->chain_info = chain_offset; + else if (chain_offset < 256) { + dp->chain_info = 2; + dp->name[len++] = chain_offset; + } else { + u32 co = cpu_to_le32(chain_offset); + memcpy(dp->name+len, &co, 4); + len += 4; + dp->chain_info = 3; + } + return len; +} + +void lafs_dir_init_block(char *block, int psz, const char *name, int len, + u32 target, int type, int chain_offset) +{ + /* create a new directory block containing just the given name. + */ + + struct dirpiece *dp; + struct dirheader *dh; + int pnum; + if (len == 0) + len = strlen(name); + BUG_ON(len > 255); + + dh = (struct dirheader *) block; + + pnum = (sizeof(struct dirheader) + (1<> psz; + + dh->root = pnum; + dh->pad = 0; + dp = dpaddr(block, pnum); + dp->target = cpu_to_le32(target); + dp->next[0] = 0; + dp->next[1] = 0; + dp->longer = Neither; + dp->length = len; + dp->type = type; + + memcpy(dp->name, name, len); + + if (chain_offset <= 1) + dp->chain_info = chain_offset; + else if (chain_offset < 256) { + dp->chain_info = 2; + dp->name[len++] = chain_offset; + } else { + u32 co = cpu_to_le32(chain_offset); + memcpy(dp->name+len, &co, 4); + len += 4; + dp->chain_info = 3; + } + + /* NOTE: we want the last piece, not the next free piece, so + * we don't add (1<lastpiece = pnum + ((offsetof(struct dirpiece, name)+len-1) >> psz); + dh->freepieces = 255 - dh->lastpiece; +} + +static inline int dir_rotate_2(char *block, int psz, u8 *treep, int dir) +{ + unsigned int B, C, D, E; + struct dirpiece *b, *d; + + B = *treep; b = dpaddr(block, B); + D = b->next[dir]; d = dpaddr(block, D); + C = d->next[1-dir]; + E = d->next[dir]; + + *treep = D; + d->next[1-dir] = B; + b->next[dir] = C; + b->longer = Neither; + d->longer = Neither; + return E; +} + +static inline int dir_rotate_3(char *block, int psz, u8 *treep, + int dir, int third) +{ + unsigned int B, F, D, C, E; + struct dirpiece *b, *f, *d; + + B = *treep; b = dpaddr(block, B); + F = b->next[dir]; f = dpaddr(block, F); + D = f->next[1-dir]; d = dpaddr(block, D); + + C = d->next[1-dir]; + E = d->next[dir]; + *treep = D; + d->next[1-dir] = B; + d->next[dir] = F; + b->next[dir] = C; + f->next[1-dir] = E; + d->longer = Neither; + b->longer = f->longer = Neither; + + if (third == Neither) + return 0; + else if (third == dir) { + b->longer = 1-dir; + return E; + } else { + f->longer = dir; + return C; + } +} + +static void dir_check_balance(char *block, int psz); +int lafs_dir_add_ent(char *block, int psz, const char *name, int len, + u32 target, int type, u32 seed, u32 hash, int hashoffset) +{ + /* Add this entry to the directory block, + * Return: + * -2 hash value is in use, same name + * -1 hash value is in use, different name + * 0 insufficient room + * 1 add successful + * + */ + struct dirheader *dh = (struct dirheader *) block; + struct dirpiece *dp, *dpold; + int piece = dh->root; + u8 *thisp = &dh->root; + u8 *topp = thisp; + int need, space; + int st; + int first, second, third; + + int depth = 0; + /* path is a list of bits indicate whether each successive step + * down from *topp was foreward(1) or backward(0). + */ + unsigned long path = 0; + + int dir; + + /* loop detect */ + int last = 0, cnt = 0, reset = 1; + + if (len == 0) + len = strlen(name); + if (piece == 0) { + /* Block is empty */ + if (type != DT_TEST) + lafs_dir_init_block(block, psz, name, len, target, + type, hashoffset); + return 1; + } + need = len + (hashoffset > 255 ? 4 : hashoffset > 1 ? 1 : 0); + need += offsetof(struct dirpiece, name); + need = DIV_ROUND_UP(need, (1<target == 0) + /* deleted entry, no AVL op needed */ + goto replace_deleted; + + if (len == dp->length && + strncmp(name, dp->name, len) == 0) + return -2; + return -1; + } + dir = (hash > hval); + if (dp->longer != Neither) { + depth = 0; + topp = thisp; + } + if (dir) + set_bit(depth, &path); + else + clear_bit(depth, &path); + depth++; + if (depth >= sizeof(path)*8) + return -2; + thisp = &dp->next[dir]; + piece = *thisp; + dp = dpaddr(block, piece); + + if (cnt > 0 && piece == last) { + return -3; + } + if (cnt == 0) { + reset += reset; + cnt = reset; + last = piece; + } + cnt--; + } + + /* Now see if there is room to store this entry, given the amount of + * sharing that we have managed to achieve + */ + if (dh->lastpiece + need > 255) + return 0; + if (type == DT_TEST) + /* Special flag to say 'just test if there is room */ + return 1; + piece = dh->lastpiece+1; + + dp = dpaddr(block, piece); + dh->lastpiece += need; + BUG_ON(dh->lastpiece == 0); + dh->freepieces -= need; + dp->target = cpu_to_le32(target); + dp->next[0] = 0; + dp->next[1] = 0; + + dp->length = len; + dp->type = type; + dp->longer = Neither; + dir_set_name(dp, name, len, hashoffset); + + /* now merge this piece into the AVL tree, rebalancing + * on the way up + */ + *thisp = piece; + + piece = *topp; + dp = dpaddr(block, piece); + + st = 0; + first = !!test_bit(0, &path); + second = !!test_bit(1, &path); + if (dp->longer == Neither) + ; + else if (dp->longer != first) { + /* took the shorter path */ + dp->longer = Neither; + piece = dp->next[first]; + st = 1; + } else if (first == second) { + /* just a two-point rotation */ + piece = dir_rotate_2(block, psz, topp, first); + st = 2; + } else { + if (depth < 3) + third = Neither; + else + third = !!test_bit(2, &path); + piece = dir_rotate_3(block, psz, topp, first, third); + st = 3; + } + + while (piece && st < depth) { + first = test_bit(st, &path) ? 1 : 0; + dp = dpaddr(block, piece); + dp->longer = first; + piece = dp->next[first]; + st++; + } + BUG_ON(dh->root == 0); + dir_check_balance(block, psz); + return 1; + +replace_deleted: + /* If there is room at the end, add an entry, + * else fail. + */ + if (dh->lastpiece + need > 255) + return 0; + if (type == DT_TEST) + return 1; + + space = dp->length + (dp->chain_info < 2 + ? 0 : (dp->chain_info == 2 + ? 1 : 4)); + space += offsetof(struct dirpiece, name); + space = DIV_ROUND_UP(space, 1<lastpiece + 1; + dpold = dp; + dp = dpaddr(block, piece); + dh->lastpiece += need; + dh->freepieces -= need; + dh->freepieces += space; + *thisp = piece; + dp->next[0] = dpold->next[0]; + dp->next[1] = dpold->next[1]; + dp->target = cpu_to_le32(target); + dp->length = len; + dp->type = type; + dir_set_name(dp, name, len, hashoffset); + return 1; +} + +int lafs_dir_del_ent(char *block, int psz, u32 seed, u32 hash) +{ + /* Delete this entry from the directory block. + * This involves removing it from the avl tree. + * If it was the last entry, we reduce 'lastpiece' + * so the space can be used immediately. + */ + + struct dirheader *dh = (struct dirheader *)block; + struct dirpiece *dp; + struct dirpiece *second; + int piece = dh->root; + u8 *thisp = &dh->root; + u8 *topp = thisp; + u8 *targetp = NULL; + u8 targetn = 0; + int space; + int dir = 0; + int depth = 0; + unsigned long path = 0; + int st = 0; + + dp = dpaddr(block, piece); + while (piece) { + u32 hval = hash_piece(seed, dp, NULL); + + if (hash == hval) { + targetp = thisp; + targetn = piece; + } + dir = (hash > hval); + if (dp->next[dir] == 0) + break; + if (dp->longer == Neither) { + topp = thisp; + depth = 0; + } else if (dp->longer == (1-dir)) { + struct dirpiece *dp2; + dp2 = dpaddr(block, dp->next[1-dir]); + if (dp2->longer == Neither) { + topp = thisp; + depth = 0; + } + } + if (dir) + set_bit(depth, &path); + else + clear_bit(depth, &path); + depth++; + if (depth >= sizeof(path)*8) + return -2; + + thisp = &dp->next[dir]; + piece = *thisp; + dp = dpaddr(block, piece); + } + if (!targetp) + return 0; + if (dir) + set_bit(depth, &path); + else + clear_bit(depth, &path); + + /* now we must walk down from topp to thisp rebalancing nodes, + * but making sure that targetp points to the link to target... + */ + + while (1) { + piece = *topp; + dir = !!test_bit(st, &path); + dp = dpaddr(block, piece); + if (dp->next[dir] == 0) + break; + + if (dp->longer == Neither) + dp->longer = 1-dir; + else if (dp->longer == dir) + dp->longer = Neither; + else { + /* need a rotation */ + second = + dpaddr(block, dp->next[1-dir]); + if (second->longer == dir) { + struct dirpiece *third = + dpaddr(block, second->next[dir]); + dir_rotate_3(block, psz, topp, 1-dir, + third->longer); + } else if (second->longer == Neither) { + dir_rotate_2(block, psz, topp, 1-dir); + dp->longer = 1-dir; + second = dpaddr(block, *topp); + second->longer = dir; + } else + dir_rotate_2(block, psz, topp, 1-dir); + if (piece == targetn) { + second = dpaddr(block, *topp); + targetp = &second->next[dir]; + } + } + topp = &dp->next[dir]; + st++; + } + + /* Ok, rebalance all done, now swap *targetp for *thisp and + * delete + */ + + piece = *thisp; + *targetp = piece; + dp = dpaddr(block, piece); + second = dpaddr(block, targetn); + *thisp = dp->next[1-dir]; + dp->next[0] = second->next[0]; + dp->next[1] = second->next[1]; + dp->longer = second->longer; + + /* now second can be destroyed */ + second->target = 0; + space = second->length + (second->chain_info < 2 + ? 0 : second->chain_info == 2 ? 1 : 4); + space += offsetof(struct dirpiece, name); + space = DIV_ROUND_UP(space, 1<root == 0) { + /* we deleted the only entry, clear the block */ + dh->lastpiece = (sizeof(struct dirheader) + (1<> psz; + dh->freepieces = 255 - dh->lastpiece; + } else if (targetn + space > dh->lastpiece) { + /* We are deleting the last entry, so it can be reused */ + dh->freepieces += dh->lastpiece+1-targetn; + dh->lastpiece = targetn-1; + } else + dh->freepieces += space; + return 1; +} + +static void dir_linearise(char *block, int psz) +{ + /* destructively linearise the entries in the block. + * i.e. arrange that for each non-deleted entry, + * ->next[0] points to the previous, and + * ->next[1] points to the next + * in sort order. + * The first points to the last, and dh->root + * points to the first + * + * Rather than using a stack to walk down, we reverse + * each pointer was we step down it, and use + * the ->longer field to say which way we came + */ + struct dirheader *dh = (struct dirheader *)block; + int piece = dh->root; + struct dirpiece *dp = NULL; + int prev = 0; + int parent = 0; + int state = 0; + int tail; + + while (piece) { + dp = dpaddr(block, piece); + switch (state) { + case 0: /* stepping down to piece for the first time */ + if (dp->next[0]) { + /* step further down */ + int t = dp->next[0]; + dp->next[0] = parent; + dp->longer = 0; + parent = piece; + piece = t; + state = 0; + } else + state = 1; + break; + case 1: /* back up from the left branch */ + /* This must be next in sequence */ + dp->next[0] = prev; + prev = piece; + if (dp->next[1]) { + /* step down the other way */ + int t = dp->next[1]; + dp->longer = 1; + dp->next[1] = parent; + parent = piece; + piece = t; + state = 0; + } else + state = 2; + break; + case 2: /* back up from the right branch */ + piece = parent; + dp = dpaddr(block, piece); + state = dp->longer; + parent = dp->next[state]; + state++; + break; + default: + BUG(); + } + } + /* now 'prev' is the last piece. Walk back along the path setting + * the forward link + */ + piece = 0; + tail = prev; + while (prev) { + dp = dpaddr(block, prev); + dp->next[1] = piece; + piece = prev; + prev = dp->next[0]; + } + dp->next[0] = tail; + dh->root = piece; +} + +struct dir_ent * +lafs_dir_extract(char *block, int psz, struct dir_ent *de, int pnum, + u32 *hash) +{ + /* extract the directory entry into de. de->name points into + * the buffer, and is not nul terminated. */ + struct dirpiece *dp = dpaddr(block, pnum); + + BUG_ON(pnum <= 0 || pnum > 255); + de->target = le32_to_cpu(dp->target); + de->type = dp->type; + de->name = dp->name; + de->nlen = dp->length; + if (hash) + *hash = hash_piece(*hash, dp, NULL); + return de; +} + +void lafs_dir_set_target(char *block, int psz, struct dir_ent *de, int pnum) +{ + /* update the target and type from de */ + struct dirpiece *dp = dpaddr(block, pnum); + dp->target = cpu_to_le32(de->target); + dp->type = de->type; +} + +void lafs_dir_split(char *orig, int psz, char *new1, char *new2, + const char *name, u32 target, int type, u32 *newhash, + u32 seed, u32 hash, int chainoffset) +{ + /* Split the orig block together with the new name, into new1 and new2. + * Linearise orig, then copy one entry into which block is least empty + * A hash somewhere between the two blocks is placed in *newhash. + * It could be the highest in 'new1' but will be less than the + * lowest in 'new2' + * + */ + struct dirheader *dh = (struct dirheader *)orig; + struct dirheader *dh1 = (struct dirheader *)new1; + struct dirheader *dh2 = (struct dirheader *)new2; + struct dirpiece *dp; + int first, last; + int full1 = 0, full2 = 0; + u32 offset, maxhash, minhash, hval; + + dir_linearise(orig, psz); + + first = dh->root; + dp = dpaddr(orig, first); + last = dp->next[0]; + if (first == 0 || last == 0) + /* orig was empty ?? */ + BUG(); + + /* create new1 and new2 with first and last */ + hval = hash_piece(seed, dp, &offset); + if (type && hash < hval) { + lafs_dir_init_block(new1, psz, name, 0, target, type, + chainoffset); + type = 0; + maxhash = hash; + } else { + lafs_dir_init_block(new1, psz, dp->name, dp->length, + le32_to_cpu(dp->target), dp->type, + offset); + maxhash = hval; + if (first == last) + first = 0; + else + first = dp->next[1]; + } + dp = dpaddr(orig, last); + hval = hash_piece(seed, dp, &offset); + if (type && hash > hval) { + lafs_dir_init_block(new2, psz, name, 0, target, type, + chainoffset); + minhash = hash; + type = 0; + } else { + BUG_ON(!first); + lafs_dir_init_block(new2, psz, dp->name, dp->length, + le32_to_cpu(dp->target), dp->type, + offset); + minhash = hval; + if (first == last) + first = 0; + else + last = dp->next[0]; + } + + while (first || type) { + /* everything from 'first' to 'last', plus 'name' (if type) + * is allowed to go in either block. + * Choose a block, and an entry, and insert it (if possible) + */ + if (full2 || (dh1->freepieces >= dh2->freepieces && !full1)) { + /* insert into new1 from first or name */ + dp = dpaddr(orig, first); + if (first) + hval = hash_piece(seed, dp, &offset); + if (type == 0 || (first && hval < hash)) { + /* first is the preferred candidate */ + if (!lafs_dir_add_ent(new1, psz, dp->name, + dp->length, + le32_to_cpu(dp->target), + dp->type, seed, hval, + offset)) + full1 = 1; + else { + maxhash = hval; + if (first == last) + first = 0; + else + first = dp->next[1]; + } + } else { + /* insert name */ + if (!lafs_dir_add_ent(new1, psz, name, 0, + target, type, seed, + hash, chainoffset)) + full1 = 1; + else { + maxhash = hash; + type = 0; + } + } + } else { + /* insert into new2 */ + dp = dpaddr(orig, last); + if (first) + hval = hash_piece(seed, dp, &offset); + if (type == 0 || (first && hval > hash)) { + /* last is the preferred candidate */ + if (!lafs_dir_add_ent(new2, psz, + dp->name, dp->length, + le32_to_cpu(dp->target), + dp->type, seed, hval, + offset)) + full2 = 1; + else { + minhash = hval; + if (first == last) + first = 0; + else + last = dp->next[0]; + } + } else { + if (!lafs_dir_add_ent(new2, psz, name, 0, + target, type, seed, + hval, chainoffset)) + full2 = 1; + else { + minhash = hash; + type = 0; + } + } + } + } + + /* newhash could be minhash, but not + * maxhash */ + *newhash = (minhash + maxhash) / 2; +} + +void lafs_dir_repack(char *block, int psz, char *new, u32 seed, int merge) +{ + struct dirheader *dh = (struct dirheader *)block; + int pnum = (sizeof(struct dirheader) + (1<>psz; + int first = !merge; + + while (pnum <= dh->lastpiece) { + int space; + struct dirpiece *dp = dpaddr(block, pnum); + + if (dp->target) { + u32 offset; + u32 hash = hash_piece(seed, dp, &offset); + if (first) + lafs_dir_init_block(new, psz, dp->name, + dp->length, + le32_to_cpu(dp->target), + dp->type, offset); + else + lafs_dir_add_ent(new, psz, dp->name, dp->length, + le32_to_cpu(dp->target), + dp->type, seed, hash, offset); + first = 0; + } + space = dp->length + (dp->chain_info < 2 + ? 0 : (dp->chain_info == 2 + ? 1 : 4)); + space += offsetof(struct dirpiece, name); + space = DIV_ROUND_UP(space, 1<root; + int cnt = 256; + + *pp = 0; + + while (pnum && cnt) { + struct dirpiece *dp = dpaddr(block, pnum); + u32 hval = hash_piece(seed, dp, NULL); + + if (hval == hash) { + *pp = pnum; + return 1; + } + + if (hash > hval) + pnum = dp->next[1]; + else { + *pp = pnum; + pnum = dp->next[0]; + } + cnt--; + } + return 0; +} + +#if 0 +static int dir_check_loop(char *block, int psz, int pnum, int depth) +{ + /* walk around the tree, and BUG if we ever get a depth > 255 */ + struct dirheader *dh = (struct dirheader *)block; + + if (pnum == -1) + pnum = dh->root; + if (depth <= 0) + return 1; + if (pnum < 0 || pnum >= 256) + BUG(); + + if (pnum) { + struct dirpiece *dp = dpaddr(block, pnum); + if (dir_check_loop(block, psz, dp->next[0], depth-1) || + dir_check_loop(block, psz, dp->next[1], depth-1)) { + printk(" ..%d(%d)\n", pnum, depth); + return 1; + } + } + return 0; +} +#endif + +int lafs_dir_empty(char *block) +{ + struct dirheader *dh = (struct dirheader *)block; + return dh->root == 0; +} + +int lafs_dir_blk_size(char *block, int psz) +{ + /* how much of this block do we actually need to store */ + struct dirheader *dh = (struct dirheader *)block; + if (lafs_dir_empty(block)) + return 0; + return (dh->lastpiece+1) << psz; +} + +/* Testing code here - no new important functionality */ +#ifndef MAIN + +static void xprintk(char *block, int psz, char *s, int a, int b, int c, int d) +{ + printk(s, a, b, c, d); + lafs_dir_print(block, psz); + BUG(); +} + +static int dir_check_depth(char *block, int psz, int p, int depth) +{ + struct dirpiece *dp = dpaddr(block, p); + int b, f; + + if (depth > 10) { + int i; + for (i = 0; i < 32; i++) + printk("%02x ", block[i]); + printk("\n"); + } + BUG_ON(depth > 10); + if (p == 0) + return 0; + b = dir_check_depth(block, psz, dp->next[0], depth+1); + f = dir_check_depth(block, psz, dp->next[1], depth+1); + if (b == f) { + if (dp->longer != Neither) + xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n", + p, b, f, dp->longer); + return b+1; + } + if (b == f-1) { + if (dp->longer != 1) + xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n", + p, b, f, dp->longer); + return f+1; + } + if (b-1 == f) { + if (dp->longer != 0) + xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n", + p, b, f, dp->longer); + return b+1; + } + xprintk(block, psz, "... %d - b=%d f=%d lgr=%d\n", p, b, f, dp->longer); + return (b > f ? b : f) + 1; +} + +static void dir_check_balance(char *block, int psz) +{ + struct dirheader *dh = (struct dirheader *) block; + dir_check_depth(block, psz, dh->root, 0); +} + +static void dir_print_piece(char *block, int psz, int piece, int depth, int dir) +{ + struct dirpiece *dp = dpaddr(block, piece); + + if (piece == 0) + return; + + dir_print_piece(block, psz, dp->next[0], depth+1, 0); + printk("%3d - %08lu:%02d %*s%c", piece, + (unsigned long) le32_to_cpu(dp->target), + depth, depth*2, "", + dir ? '\\' : '/'); + + printk("%.*s\n", dp->length, dp->name); + dir_print_piece(block, psz, dp->next[1], depth+1, 1); +} + +static void dir_print_block(char *block, int psz, int sort) +{ + struct dirheader *dh; + struct dirpiece *dp; + + dh = (struct dirheader *)block; + printk("===Directory Block===\n"); + + printk(" Root: %d\n", dh->root); + printk(" Last Piece : %d (%d left)\n", dh->lastpiece, + 255 - dh->lastpiece); + printk(" Free Pieces: %d (%d deleted)\n", dh->freepieces, + dh->freepieces - (255 - dh->lastpiece)); + if (sort == 1) + dir_print_piece(block, psz, dh->root, 0, 1); + else if (sort == 2) { + /* linearised */ + int pnum = dh->root; + while (pnum) { + dp = dpaddr(block, pnum); + printk("%3d - %08lu: (b:%-3d, f:%-3d, l:%d, type:%d ", + pnum, (unsigned long) le32_to_cpu(dp->target), + dp->next[0], dp->next[1], dp->longer, + dp->type); + printk(": (%d)%.*s\n", dp->length, dp->length, + dp->name); + pnum = dp->next[1]; + } + } else { + /* don't interpret the pieces too much */ + int pnum = (sizeof(struct dirheader) + (1<>psz; + while (pnum <= dh->lastpiece) { + dp = dpaddr(block, pnum); + printk("%3d - %08lu: (b:%-3d, f:%-3d, l:%d, type:%d ", + pnum, (unsigned long)le32_to_cpu(dp->target), + dp->next[0], dp->next[1], dp->longer, + dp->type); + printk(": (%d)%.*s\n", dp->length, + dp->length, dp->name); + pnum += (offsetof(struct dirpiece, name) + + dp->length + (1<>psz; + } + } +} + +void lafs_dir_print(char *buf, int psz) +{ + dir_print_block(buf, psz, 1); +} +#endif + +#ifdef MAIN + +int noise; +int main(int argc, char **argv) +{ + char block[4096]; + int blenshift = 10; + int psz = blenshift - 8; + int arg = 2; + char nm[256]; + + lafs_dir_init_block(block, psz, argv[1], 0, 42, 3, 0); + while (arg < argc-1) { + if (argv[arg][0] != '-') + switch (lafs_dir_add_ent(block, psz, argv[arg], 0, + 42+arg, 4, 0)) { + case 0: + printf("%s didn't fit!\n", argv[arg]); + break; + case -1: + printf("%s already exists\n", argv[arg]); + break; + case 1: + printf("%s inserted\n", argv[arg]); + } + else + switch (lafs_dir_del_ent(block, psz, argv[arg]+1, 0)) { + case 0: + printf("%s not found!\n", argv[arg]); + break; + case -2: + printf("%s not deleted - bad dir\n", argv[arg]); + break; + case 1: + printf("%s deleted\n", argv[arg]); + break; + } + + dir_check_balance(block, psz); + arg++; + } + dir_print_block(block, psz, 0); + dir_print_block(block, psz, 1); + + lafs_dir_split(block, psz, block+1024, block+2048, argv[arg], + 40, 2, nm); + dir_print_block(block+1024, psz, 1); + dir_print_block(block+2048, psz, 1); + dir_get_prefix(block+1024, block+2048, psz, block+3096); + printf("Prefix is <%s>\n", block+3096); + lafs_dir_repack(block+1024, psz, block, 0); + lafs_dir_repack(block+2048, psz, block, 1); + printf("============= repacked ===================\n"); + dir_print_block(block, psz, 1); + exit(0); +} +#endif diff --git a/lib/internal.h b/lib/internal.h index 464804e..7f16b74 100644 --- a/lib/internal.h +++ b/lib/internal.h @@ -46,3 +46,47 @@ unsigned long crc32( #define encode16(p,n) ({ *(p++) = (n)&255; *(p++) = ((n)>>8) & 255; }) #define encode32(p,n) ({ encode16(p,n); encode16(p, ((n)>>16)); }) #define encode48(p,n) ({ encode32(p,n); encode16(p, ((n)>>32)); }) + +struct dir_ent { + char *name; + int nlen; + u32 target; + int type; +}; +struct dir_ent * +lafs_dir_extract(char *block, int psz, struct dir_ent *de, int pnum, + u32 *hash); +void lafs_dir_set_target(char *block, int psz, struct dir_ent *de, int pnum); +void lafs_dir_print(char *buf, int psz); +#define DT_TEST 128 /* for dir_add_ent, this flags to test for space, but not do + * any actual add + */ +#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) + +#define le32_to_cpu __le32_to_cpu +#define cpu_to_le32 __cpu_to_le32 +#define printk printf + +static inline void BUG_ON(int cond) +{ + if (cond) + abort(); +} +static inline void BUG(void) +{ + BUG_ON(1); +} +static inline void set_bit(int bit, unsigned long *map) +{ + *map |= 1UL< +#include +#include "internal.h" + +int lafs_dir_next(struct lafs_ino *dir, u32 *indexp, char *name, + u32 *inop, int *typep) +{ + /* Find the first entry after *indexp, and set indexp, + * name, inop, typep to that entry. + * Return 0 on success or 1 if no more entries. + * If called with *indexp == -1, look for first entry. + */ + u32 hash = *indexp + 1; + + do { + struct lafs_dblk *db; + u32 block; + u8 piece; + struct dir_ent de; + block = lafs_find_next(dir, hash+1); + if (block == LAFS_NOBLOCK) + block = 0; + + db = lafs_dblk(dir, block); + if (!db || + lafs_load_dblk(db)) + return -1; + + while (1) { + lafs_dir_find(db->b.data, dir->fs->blockbits-8, + dir->md.file.seed, + hash, &piece); + *indexp = dir->md.file.seed; + if (piece && + lafs_dir_extract(db->b.data, dir->fs->blockbits-8, &de, + piece, indexp)->target == 0) + hash = *indexp +1; + else + break; + } + if (piece) { + if (de.target) { + strncpy(name, de.name, de.nlen); + name[de.nlen] = 0; + *inop = de.target; + *typep = de.type; + return 1; + } + } + hash = block; + } while (hash); + return 0; +} diff --git a/lib/lafs_find_dblk.c b/lib/lafs_find_dblk.c index 52cfc2f..0f744d1 100644 --- a/lib/lafs_find_dblk.c +++ b/lib/lafs_find_dblk.c @@ -13,9 +13,10 @@ #include #include #include +#include "internal.h" -static u64 leaf_lookup(unsigned char *buf, int len, u32 startaddr, - u32 target, u32 *nextp); +u64 lafs_leaf_lookup(unsigned char *buf, int len, u32 startaddr, + u32 target, u32 *nextp); int lafs_find_dblk(struct lafs_dblk *db) { @@ -44,27 +45,18 @@ int lafs_find_dblk(struct lafs_dblk *db) return 0; } - db->b.physaddr = leaf_lookup((unsigned char*)ino->dblock->b.data + ino->metadata_size, - fs->blocksize - ino->metadata_size, - 0, - db->b.fileaddr, - NULL); + db->b.physaddr = lafs_leaf_lookup( + (unsigned char*)ino->dblock->b.data + ino->metadata_size, + fs->blocksize - ino->metadata_size, + 0, + db->b.fileaddr, + NULL); return 0; } -/* - * extract little-endian values out of memory. - * Each function is given a char*, and moves it forwards - */ - -#define decode16(p) ({ unsigned int _a; _a= (unsigned char)*(p++); _a + (((unsigned char)*p++)<<8); }) -#define decode32(p) ({ long _b; _b = decode16(p); _b + ((u32)decode16(p)<<16); }) -#define decode48(p) ({ u64 _c; _c = decode32(p); _c + ((u64)decode16(p)<<32); }) - - -uint64_t leaf_lookup(unsigned char *buf, int len, u32 startaddr, - u32 target, u32 *nextp) +uint64_t lafs_leaf_lookup(unsigned char *buf, int len, u32 startaddr, + u32 target, u32 *nextp) { /* buf starts with a 2byte header * if 1, then 4 byte offset followed by 6byte littleending indirect entries. @@ -75,8 +67,11 @@ uint64_t leaf_lookup(unsigned char *buf, int len, u32 startaddr, int hi,lo; int elen; u32 addr, next; - if (nextp) *nextp = NoBlock; - if (buf[1]) return 0; + + if (nextp) + *nextp = NoBlock; + if (buf[1]) + return 0; switch (buf[0]) { default: p = 0; break; diff --git a/lib/lafs_find_next.c b/lib/lafs_find_next.c new file mode 100644 index 0000000..4afa224 --- /dev/null +++ b/lib/lafs_find_next.c @@ -0,0 +1,78 @@ + +#include + +static int __block_find_next(struct lafs_ino *inode, u32 *addrp); + +u32 lafs_find_next(struct lafs_ino *inode, u32 addr) +{ + /* Find the first allocated block in 'ino' + * which is at-or-after 'bnum'. + p* making sure to skip over Recent hole. + */ + while(1) { + int rv = __block_find_next(inode, &addr); + struct lafs_dblk *b; + if (rv == 0) + return LAFS_NOBLOCK; + if (rv == 2) + continue; + b = lafs_dblk(inode, addr); + addr++; + } +} + +static int __block_find_next(struct lafs_ino *inode, u32 *addrp) +{ + /* find the next allocated block in inode at or after '*addrp' + * and set *addrp. + * Return: + * 0 - there is no block at or after *addrp + * 1 - Yes, *addrp exists + * 2 - *addrp has been updated, check again + */ + struct lafs_iblk *leaf; + u32 nexti, nextd; + u64 p; + int offset; + struct lafs_blk *b; + u32 addr = *addrp; + int rv = 0; + + if (inode->depth == 0) { + if (addr == 0) + return 1; + lafs_make_iblock(inode); + leaf = inode->iblock; + } else { + unsigned char *buf; + leaf = lafs_leaf_find(inode, addr, 0, &nexti); + if (nexti != LAFS_NOBLOCK) + rv = 2; + offset = 0; + buf = (unsigned char *)leaf->b.data; + if (inode->depth == 1) { + offset = inode->metadata_size; + buf = (unsigned char *)leaf->b.ino->dblock->b.data; + } + p = lafs_leaf_lookup(buf + offset, + inode->fs->blocksize - offset, leaf->b.fileaddr, + addr, &nextd); + if (p) + return 1; + + if (nextd == LAFS_NOBLOCK) + nextd = nexti; + else + rv = 1; + } + list_for_each_entry(b, &leaf->children, siblings) { + if (b->fileaddr >= addr + && b->fileaddr < nextd + && (b->flags & B_Valid)) { + nextd = b->fileaddr; + rv = 1; + } + } + *addrp = nextd; + return rv; +} diff --git a/lib/lafs_leaf_find.c b/lib/lafs_leaf_find.c new file mode 100644 index 0000000..8e8d684 --- /dev/null +++ b/lib/lafs_leaf_find.c @@ -0,0 +1,112 @@ +#include + +struct lafs_iblk *lafs_leaf_find(struct lafs_ino *inode, + u32 addr, int adopt, u32 *next) +{ + /* Find the leaf index block which refers to this address (if any do) + */ +#if 0 + struct lafs_iblk *ib, *ib2; + int depth; + u64 iphys; + u32 iaddr; +#endif + if (next) + *next = LAFS_NOBLOCK; + + /* now check out addressing from the inode */ + if (inode == NULL || inode->depth <= 1) { + /* Data or leaf indexing is in inode. + */ + lafs_make_iblock(inode); + return inode->iblock; + } + +#if 0 + /* depth is >= 2, so the inode contains indexes. + * find the appropriate index, find the relevant index block, + * load it, and see what's there... */ + depth = inode->depth - 1; + iphys = index_lookup((unsigned char*)inode->dblock->data + inode->metadata_size, + fs->blocksize - inode->metadata_size, + addr, + &iaddr, next); + + /* FIXME if there is corruption, iphys could be zero which will + * cause problems soon + */ + if (iphys==0) abort(); + + if (iaddr > 1000000) abort(); + ib = block_ifind(fs, inode, iaddr, depth, iphys); + + if (! (ib->flags & B_Linked)) { + /* need to check for peers */ + ib2 = peer_find(fs, inode->filesys, inode, iaddr, inode->depth-1,iphys); + if (ib2) + list_add(&ib->peers, &ib2->peers); + ib->flags |= B_Linked; + } + if (adopt) { + inode_make_iblock(fs, inode, adopt); + block_adopt(ib, inode->iblock); + } + load_block(fs, ib); + /* this block may not be the parent we want. It may have been split already. + * If it has, other blocks will be immediately afterwards in the sibling + * list. So we walk down the sibling list until we find a block that + * is before ib or after addr, and we keep the block before that. + */ + if (ib->parent) + while(!list_empty(&ib->siblings) /* HACK FIXME */) { + struct block *nxt; + + if (ib->siblings.next == &iblk(ib->parent)->children) + break; + nxt = list_entry(ib->siblings.next, struct block, siblings); + if (nxt->fileaddr < ib->fileaddr || nxt->fileaddr > addr) + break; + getref(nxt); putref(ib); + ib = nxt; + } + + while (depth > 1) { + depth--; + /* ib contains indexes, so repeat what we did above */ + iphys = index_lookup((unsigned char*)ib->data, fs->blocksize, addr, &iaddr, next); + ib2 = block_ifind(fs, inode, iaddr, depth, iphys); + if (!(ib2->flags & B_Linked)) { + struct block *b2 = peer_find(fs, inode->filesys, + inode, iaddr, + depth, iphys); + if (b2) + list_add(&ib2->peers, &b2->peers); + ib2->flags |= B_Linked; + } + load_block(fs, ib2); + while(ib2->parent) { + struct block *nxt; + if (ib2->siblings.next == &iblk(ib2->parent)->children) + break; + nxt = list_entry(ib2->siblings.next, struct block, siblings); + if (nxt->fileaddr < ib2->fileaddr || nxt->fileaddr > addr) + break; + getref(nxt); + putref(ib2); + ib2 = nxt; + } + if(adopt) { + block_lock(ib); /* FIXME error check */ + block_adopt(ib2, ib); + } + putref(ib); + ib = ib2; + } + /* ib contains leaf indexing, either indirect or extent + * see above + */ + return ib; +#else + return NULL; +#endif +} diff --git a/tools/lafs.c b/tools/lafs.c index d461a64..94f3563 100644 --- a/tools/lafs.c +++ b/tools/lafs.c @@ -1428,6 +1428,51 @@ static void c_store(struct state *st, void **args) printf("Oh how I wish I could copy %s to %s\n", from, to); } +/****** LS ******/ +//static char *types[16] = { "unknown","FIFO","CHR","3","DIR","5","BLK","7","REG","9","LNK","11","SOCK","13","WHT","15"}; +static char ctypes[] = "?pc3d5b7-9lBsDWF"; +static char help_ls[] = "List files in a directory"; +static struct args args_ls[] = { + {"DIRECTORY", internal, -1, {NULL}, "Directory to list"}, + {"-long", flag, -1, {NULL}, "Get a long, detailed listing"}, + TERMINAL_ARG +}; +static void c_ls(struct state *st, void **args) +{ + struct lafs_ino *ino; + u32 index = -1; + char name[257]; + u32 inum; + int type; + int col; + + if (st->lafs->ss.root == 0) { + printf("ls: filesytem not ready\n"); + return; + } + ino = lafs_get_itable(st->lafs); + ino = lafs_get_inode(ino, 2); + + col = 0; + while (lafs_dir_next(ino, &index, name, &inum, &type) == 1) { + if (args[2]) { + printf("%5lu %cxxxxxxxxx %s\n", + (unsigned long)inum, ctypes[type], name); + } else { + printf("%-12s ", name); + col += 13; + if (col > 60) { + printf("\n"); + col = 0; + } + } + if (index+1 == 0) + break; + } + if (args[2] == NULL && col) + printf("\n"); +} + /* list of all commands - preferably in alphabetical order */ #define CMD(x) {#x, c_##x, args_##x, help_##x} static struct cmd lafs_cmds[] = { @@ -1436,6 +1481,7 @@ static struct cmd lafs_cmds[] = { CMD(exit), CMD(help), CMD(load_dev), + CMD(ls), CMD(mount), CMD(newfs), CMD(quit), -- 2.39.5