dir-avl.c

   1 /*
   2  * A directory block is stored as an AVL tree.
   3  * Entries are added to the end, and merged into
   4  * the AVL tree.
   5  * Deleted entries are left in place, but marked
   6  * as deleted (pointer is 0)
   7  * When a block becomes full, we re-pack it,
   8  * or split it.
   9  *
  10  */
  11 #include "lafs.h"
  12
  13 /* TEA_transform borrowed from ext3 */
  14 #define DELTA 0x9E3779B9
  15
  16 static void TEA_transform(u32 buf[2], u32 const in[4])
  17 {
  18         u32     sum = 0;
  19         u32     b0 = buf[0], b1 = buf[1];
  20         u32     a = in[0], b = in[1], c = in[2], d = in[3];
  21         int     n = 16;
  22
  23         do {
  24                 sum += DELTA;
  25                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  26                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  27         } while(--n);
  28
  29         buf[0] += b0;
  30         buf[1] += b1;
  31 }
  32
  33 static void str2msg(u32 *msg, int len, const char *name)
  34 {
  35         int i;
  36         u32 part = 0;
  37         int pad = len;
  38
  39         if (len > 16)
  40                 len = 16;
  41         for (i = 0; i < len ; i++) {
  42                 part = (part << 8) + name[i];
  43                 if ((i%4) == 3)
  44                         *msg++ = part;
  45         }
  46         for ( ; i < 16 ; i++) {
  47                 part = (part<<8) + pad;
  48                 if ((i%4) == 3)
  49                         *msg++ = part;
  50         }
  51 }
  52
  53 int lafs_hash_name(u32 seed, int len, const char *name)
  54 {
  55         u32 buf[2];
  56         u32 msg[4];
  57         buf[0] = seed;
  58         buf[1] = ~seed;
  59
  60         switch (seed & 0x7) {
  61         default:
  62                 return 0;
  63         case 0:
  64                 return 1;
  65         case 1:
  66                 while (len > 0) {
  67                         str2msg(msg, len, name);
  68                         TEA_transform(buf, msg);
  69                         len -= 16;
  70                         name += 16;
  71                 }
  72                 return buf[0] & 0x7fffffff;
  73         }
  74 }
  75
  76 static u32 hash_piece(u32 seed, struct dirpiece *dp, u32 *offsetp)
  77 {
  78         u32 hash = lafs_hash_name(seed, dp->length, dp->name);
  79         u32 offset = 0;
  80         switch (dp->chain_info) {
  81         case 0:
  82                 break;
  83         case 1:
  84                 offset = 1;
  85                 break;
  86         case 2:
  87                 offset = (unsigned char) dp->name[dp->length];
  88                 break;
  89         case 3:
  90                 memcpy(&offset, dp->name + dp->length, 4);
  91                 offset = le32_to_cpu(offset);
  92                 break;
  93         }
  94         if (offsetp) *offsetp = offset;
  95         return hash + offset;
  96 }
  97
  98
  99 /* dpaddr assumes that 'psz' (piece size) is valid when called */
 100 #define dpaddr(_block, _piece) ((struct dirpiece*)((_block) + ((_piece)<<psz)))
 101 #define dlpaddr(_block, _piece) ((struct dirleafpiece*)((_block) + ((_piece)<<psz)))
 102
 103 static int dir_set_name(struct dirpiece *dp, const char *name, int len,
 104                          int chain_offset)
 105 {
 106         memcpy(dp->name, name, len);
 107
 108         if (chain_offset <= 1)
 109                 dp->chain_info = chain_offset;
 110         else if (chain_offset < 256) {
 111                 dp->chain_info = 2;
 112                 dp->name[len++] = chain_offset;
 113         } else {
 114                 u32 co = cpu_to_le32(chain_offset);
 115                 memcpy(dp->name+len, &co, 4);
 116                 len += 4;
 117                 dp->chain_info = 3;
 118         }
 119         return len;
 120 }
 121
 122 void lafs_dir_init_block(char *block, int psz, const char *name, int len,
 123                          u32 target, int type, int chain_offset)
 124 {
 125         /* create a new directory block containing just the given name.
 126          */
 127
 128         struct dirpiece *dp;
 129         struct dirheader *dh;
 130         int pnum;
 131         if (len == 0)
 132                 len = strlen(name);
 133         BUG_ON(len > 255);
 134
 135         dh = (struct dirheader*) block;
 136
 137         pnum = (sizeof(struct dirheader)+ (1<<psz)-1) >> psz;
 138
 139         dh->root = pnum;
 140         dh->pad = 0;
 141         dp = dpaddr(block, pnum);
 142         dp->target = cpu_to_le32(target);
 143         dp->next[0] = 0;
 144         dp->next[1] = 0;
 145         dp->longer = Neither;
 146         dp->length = len;
 147         dp->type = type;
 148
 149         memcpy(dp->name, name, len);
 150
 151         if (chain_offset <= 1)
 152                 dp->chain_info = chain_offset;
 153         else if (chain_offset < 256) {
 154                 dp->chain_info = 2;
 155                 dp->name[len++] = chain_offset;
 156         } else {
 157                 u32 co = cpu_to_le32(chain_offset);
 158                 memcpy(dp->name+len, &co, 4);
 159                 len += 4;
 160                 dp->chain_info = 3;
 161         }
 162
 163         /* NOTE: we want the last piece, not the next free piece, so we don't add
 164          * (1<<psz) into this sum
 165          */
 166         dh->lastpiece = pnum + ((offsetof(struct dirpiece, name)+len-1)>> psz);
 167         dh->freepieces = 255 - dh->lastpiece;
 168 }
 169
 170
 171
 172
 173 static inline int dir_rotate_2(char *block, int psz, u8 *treep, int dir)
 174 {
 175         unsigned int B,C,D,E;
 176         struct dirpiece *b,*d;
 177
 178         B = *treep;             b = dpaddr(block, B);
 179         D = b->next[dir];       d = dpaddr(block, D);
 180         C = d->next[1-dir];
 181         E = d->next[dir];
 182
 183         *treep = D;
 184         d->next[1-dir] = B;
 185         b->next[dir] = C;
 186         b->longer = Neither;
 187         d->longer = Neither;
 188         return E;
 189 }
 190
 191 static inline int dir_rotate_3(char *block, int psz, u8 *treep, int dir, int third)
 192 {
 193         unsigned int B, F, D, C, E;
 194         struct dirpiece *b, *f, *d;
 195
 196         B = *treep;             b = dpaddr(block, B);
 197         F = b->next[dir];       f = dpaddr(block, F);
 198         D = f->next[1-dir];     d = dpaddr(block, D);
 199
 200         C = d->next[1-dir];
 201         E = d->next[dir];
 202         *treep = D;
 203         d->next[1-dir] = B;
 204         d->next[dir] = F;
 205         b->next[dir] = C;
 206         f->next[1-dir] = E;
 207         d->longer = Neither;
 208         b->longer = f->longer = Neither;
 209
 210         if (third == Neither)
 211                 return 0;
 212         else if (third == dir) {
 213                 b->longer = 1-dir;
 214                 return E;
 215         } else {
 216                 f->longer = dir;
 217                 return C;
 218         }
 219 }
 220
 221 static void dir_check_balance(char *block, int psz);
 222 int lafs_dir_add_ent(char *block, int psz, const char *name, int len, u32 target,
 223                      int type, u32 seed, u32 hash, int hashoffset)
 224 {
 225         /* Add this entry to the directory block,
 226          * Return:
 227          *   -2   hash value is in use, same name
 228          *   -1   hash value is in use, different name
 229          *    0   insufficient room
 230          *    1   add successful
 231          *
 232          */
 233         struct dirheader *dh = (struct dirheader*) block;
 234         struct dirpiece *dp, *dpold;
 235         int piece = dh->root;
 236         u8 *thisp = &dh->root;
 237         u8 *topp = thisp;
 238         int need, space;
 239         int st;
 240         int first, second, third;
 241
 242         int depth = 0;
 243         /* path is a list of bits indicate whether each successive step
 244          * down from *topp was foreward(1) or backward(0).
 245          */
 246         unsigned long path = 0;
 247
 248         int dir;
 249
 250         /* loop detect */
 251         int last=0, cnt=0, reset=1;
 252
 253         if (len==0)
 254                 len = strlen(name);
 255         if (piece==0) {
 256                 /* Block is empty */
 257                 if (type != DT_TEST)
 258                         lafs_dir_init_block(block, psz, name, len, target,
 259                                             type, hashoffset);
 260                 return 1;
 261         }
 262         need = len + (hashoffset > 255 ? 4 : hashoffset > 1 ? 1 : 0);
 263         need += offsetof(struct dirpiece, name);
 264         need = DIV_ROUND_UP(need, (1<<psz));
 265
 266         /* First, find the insertion point */
 267         dp = dpaddr(block, piece);
 268         while(piece) {
 269                 u32 hval = hash_piece(seed, dp, NULL);
 270
 271                 if (hval == hash) {
 272                         if (dp->target == 0)
 273                                 /* deleted entry, no AVL op needed */
 274                                 goto replace_deleted;
 275
 276                         if (len == dp->length &&
 277                             strncmp(name, dp->name, len) == 0)
 278                                 return -2;
 279                         return -1;
 280                 }
 281                 dir = (hash > hval);
 282                 if (dp->longer != Neither) { depth = 0; topp = thisp;}
 283                 if (dir) set_bit(depth, &path);
 284                 else clear_bit(depth, &path);
 285                 depth++;
 286                 if (depth >= sizeof(path)*8) return -2;
 287                 thisp = &dp->next[dir];
 288                 piece = *thisp;
 289                 dp = dpaddr(block, piece);
 290
 291                 if (cnt > 0 && piece == last) {
 292                         printk("LOOP\n");
 293                         return -3;
 294                 }
 295                 if (cnt == 0) {
 296                         reset += reset;
 297                         cnt = reset;
 298                         last = piece;
 299                 }
 300                 cnt--;
 301         }
 302
 303         /* Now see if there is room to store this entry, given the amount of
 304          * sharing that we have managed to achieve
 305          */
 306         if (dh->lastpiece + need > 255)
 307                 return 0;
 308         if (type == DT_TEST)
 309                 /* Special flag to say 'just test if there is room */
 310                 return 1;
 311         piece = dh->lastpiece+1;
 312 /*      printf("inserting %s at %d, sharelen %d\n", name, piece, sharelen);*/
 313         dp = dpaddr(block, piece);
 314         dh->lastpiece += need;
 315         BUG_ON(dh->lastpiece==0);
 316         dh->freepieces -= need;
 317         dp->target = cpu_to_le32(target);
 318         dp->next[0] = 0;
 319         dp->next[1] = 0;
 320
 321         dp->length = len;
 322         dp->type = type;
 323         dp->longer = Neither;
 324         dir_set_name(dp, name, len, hashoffset);
 325
 326         /* now merge this piece into the AVL tree, rebalancing
 327          * on the way up
 328          */
 329         *thisp = piece;
 330
 331         piece = *topp;
 332         dp = dpaddr(block, piece);
 333
 334         st = 0;
 335         if (dp->longer == Neither)
 336                 ;
 337         else if (dp->longer != (first = !!test_bit(0, &path))) {
 338                 /* took the shorter path */
 339                 dp->longer = Neither;
 340                 piece = dp->next[first];
 341                 st = 1;
 342         } else if (first == (second = !!test_bit(1, &path))) {
 343                 /* just a two-point rotation */
 344                 piece = dir_rotate_2(block, psz, topp, first);
 345                 st = 2;
 346         } else {
 347                 if (depth < 3) third = Neither;
 348                 else third = !!test_bit(2, &path);
 349                 piece = dir_rotate_3(block, psz, topp, first, third);
 350                 st = 3;
 351         }
 352
 353         while (piece && st < depth) {
 354                 first = test_bit(st, &path) ? 1 : 0;
 355                 dp = dpaddr(block, piece);
 356                 dp->longer = first;
 357                 piece = dp->next[first];
 358                 st++;
 359         }
 360         BUG_ON(dh->root == 0);
 361         dir_check_balance(block, psz);
 362         return 1;
 363
 364  replace_deleted:
 365         /* If there is room at the end, add an entry,
 366          * else fail.
 367          */
 368         if (dh->lastpiece + need > 255)
 369                 return 0;
 370         if (type == DT_TEST)
 371                 return 1;
 372
 373         space = dp->length + (dp->chain_info < 2 ? 0 : dp->chain_info == 2 ? 1 : 4);
 374         space += offsetof(struct dirpiece, name);
 375         space = DIV_ROUND_UP(space, 1<<psz);
 376
 377         piece = dh->lastpiece + 1;
 378         dpold = dp;
 379         dp = dpaddr(block, piece);
 380         dh->lastpiece += need;
 381         dh->freepieces -= need;
 382         dh->freepieces += space;
 383         *thisp = piece;
 384         dp->next[0] = dpold->next[0];
 385         dp->next[1] = dpold->next[1];
 386         dp->target = cpu_to_le32(target);
 387         dp->length = len;
 388         dp->type = type;
 389         dir_set_name(dp, name, len, hashoffset);
 390         return 1;
 391 }
 392
 393 int lafs_dir_del_ent(char *block, int psz, u32 seed, u32 hash)
 394 {
 395         /* Delete this entry from the directory block.
 396          * This involves either it from the avl tree.
 397          * If it was the last entry, we reduce 'lastpiece'
 398          * so the space can be used immediately.
 399          */
 400
 401         struct dirheader *dh = (struct dirheader*)block;
 402         struct dirpiece *dp;
 403         struct dirpiece *second;
 404         int piece = dh->root;
 405         u8 *thisp = &dh->root;
 406         u8 *topp = thisp;
 407         u8 *targetp = NULL;
 408         u8 targetn = 0;
 409         int space;
 410         int dir = 0;
 411         int depth = 0;
 412         unsigned long path = 0;
 413         int st = 0;
 414
 415         dp = dpaddr(block, piece);
 416         while (piece) {
 417                 u32 hval = hash_piece(seed, dp, NULL);
 418
 419                 if (hash == hval) {
 420                         targetp = thisp;
 421                         targetn = piece;
 422                 }
 423                 dir = (hash > hval);
 424                 if (dp->next[dir] == 0)
 425                         break;
 426                 if (dp->longer == Neither) {
 427                         topp = thisp;
 428                         depth = 0;
 429                 } else if (dp->longer == (1-dir)) {
 430                         struct dirpiece *dp2;
 431                         dp2 = dpaddr(block, dp->next[1-dir]);
 432                         if (dp2->longer == Neither) {
 433                                 topp = thisp;
 434                                 depth = 0;
 435                         }
 436                 }
 437                 if (dir) set_bit(depth, &path);
 438                 else clear_bit(depth, &path);
 439                 depth ++;
 440                 if (depth >= sizeof(path)*8) return -2;
 441
 442                 thisp = &dp->next[dir];
 443                 piece = *thisp;
 444                 dp = dpaddr(block, piece);
 445         }
 446         if (!targetp)
 447                 return 0;
 448         if (dir) set_bit(depth, &path);
 449         else clear_bit(depth, &path);
 450
 451         /* now we must walk down from topp to thisp rebalancing nodes,
 452          * but making sure that targetp points to the link to target...
 453          */
 454
 455         while (1) {
 456                 piece = *topp;
 457                 dir = !!test_bit(st, &path);
 458                 dp = dpaddr(block, piece);
 459                 if (dp->next[dir] == 0) break;
 460
 461                 if (dp->longer == Neither)
 462                         dp->longer = 1-dir;
 463                 else if (dp->longer == dir)
 464                         dp->longer = Neither;
 465                 else {
 466                         /* need a rotation */
 467                         second =
 468                                 dpaddr(block, dp->next[1-dir]);
 469                         if (second->longer == dir) {
 470                                 struct dirpiece *third =
 471                                         dpaddr(block, second->next[dir]);
 472                                 dir_rotate_3(block, psz, topp, 1-dir,
 473                                              third->longer);
 474                         } else if (second->longer == Neither) {
 475                                 dir_rotate_2(block, psz, topp, 1-dir);
 476                                 dp->longer = 1-dir;
 477                                 second = dpaddr(block, *topp);
 478                                 second->longer = dir;
 479                         } else
 480                                 dir_rotate_2(block, psz, topp, 1-dir);
 481                         if (piece == targetn) {
 482                                 second = dpaddr(block, *topp);
 483                                 targetp = &second->next[dir];
 484                         }
 485                 }
 486                 topp = &dp->next[dir];
 487                 st++;
 488         }
 489
 490         /* Ok, rebalance all done, now swap *targetp for *thisp and
 491          * delete
 492          */
 493
 494         piece = *thisp;
 495         *targetp = piece;
 496         dp = dpaddr(block, piece);
 497         second = dpaddr(block, targetn);
 498         *thisp = dp->next[1-dir];
 499         dp->next[0] = second->next[0];
 500         dp->next[1] = second->next[1];
 501         dp->longer = second->longer;
 502
 503         /* now second can be destroyed */
 504         second->target = 0;
 505         space = second->length + (second->chain_info < 2
 506                                   ? 0 : second->chain_info == 2 ? 1 : 4);
 507         space += offsetof(struct dirpiece, name);
 508         space = DIV_ROUND_UP(space, 1<<psz);
 509         if (dh->root == 0) {
 510                 /* we deleted the only entry, clear the block */
 511                 dh->lastpiece = (sizeof(struct dirheader)+ (1<<psz)-1) >> psz;
 512                 dh->freepieces = 255 - dh->lastpiece;
 513         } else if (targetn + space > dh->lastpiece) {
 514                 /* We are deleting the last entry, so it can be reused */
 515                 dh->freepieces += dh->lastpiece+1-targetn;
 516                 dh->lastpiece = targetn-1;
 517         } else
 518                 dh->freepieces += space;
 519         return 1;
 520 }
 521
 522 static void dir_linearise(char *block, int psz)
 523 {
 524         /* destructively linearise the entries in the block.
 525          * i.e. arrange that for each non-deleted entry,
 526          * ->next[0] points to the previous, and
 527          * ->next[1] points to the next
 528          * in sort order.
 529          * The first points to the last, and dh->root
 530          * points to the first
 531          *
 532          * Rather than using a stack to walk down, we reverse
 533          * each pointer was we step down it, and use
 534          * the ->longer field to say which way we came
 535          */
 536         struct dirheader *dh = (struct dirheader*)block;
 537         int piece = dh->root;
 538         struct dirpiece *dp = NULL;
 539         int prev = 0;
 540         int parent = 0;
 541         int state = 0;
 542         int tail;
 543
 544         while (piece) {
 545                 dp = dpaddr(block, piece);
 546                 switch(state) {
 547                 case 0: /* stepping down to piece for the first time */
 548                         if (dp->next[0]) {
 549                                 /* step further down */
 550                                 int t = dp->next[0];
 551                                 dp->next[0] = parent;
 552                                 dp->longer = 0;
 553                                 parent = piece;
 554                                 piece = t;
 555                                 state = 0;
 556                         } else
 557                                 state = 1;
 558                         break;
 559                 case 1: /* back up from the left branch */
 560                         /* This must be next in sequence */
 561                         dp->next[0] = prev;
 562                         prev = piece;
 563                         if (dp->next[1]) {
 564                                 /* step down the other way */
 565                                 int t= dp->next[1];
 566                                 dp->longer = 1;
 567                                 dp->next[1] = parent;
 568                                 parent = piece;
 569                                 piece = t;
 570                                 state = 0;
 571                         } else
 572                                 state = 2;
 573                         break;
 574                 case 2: /* back up from the right branch */
 575                         piece = parent;
 576                         dp = dpaddr(block, piece);
 577                         state = dp->longer;
 578                         parent = dp->next[state];
 579                         state++;
 580                         break;
 581                 default: BUG();
 582                 }
 583         }
 584         /* now 'prev' is the last piece. Walk back along the path setting
 585          * the forward link
 586          */
 587         piece = 0;
 588         tail = prev;
 589         while (prev) {
 590                 dp = dpaddr(block, prev);
 591                 dp->next[1] = piece;
 592                 piece = prev;
 593                 prev = dp->next[0];
 594         }
 595         dp->next[0] = tail;
 596         dh->root = piece;
 597 }
 598
 599 struct dir_ent *
 600 lafs_dir_extract(char *block, int psz, struct dir_ent *de, int pnum,
 601                  u32 *hash)
 602 {
 603         /* extract the directory entry into de.  de->name points into
 604          * the buffer, and is not nul terminated. */
 605         struct dirpiece *dp = dpaddr(block, pnum);
 606
 607         BUG_ON(pnum <= 0 || pnum > 255);
 608         de->target = le32_to_cpu(dp->target);
 609         de->type = dp->type;
 610         de->name = dp->name;
 611         de->nlen = dp->length;
 612         if (hash)
 613                 *hash = hash_piece(*hash, dp, NULL);
 614         return de;
 615 }
 616
 617 void lafs_dir_set_target(char *block, int psz, struct dir_ent *de, int pnum)
 618 {
 619         /* update the target and type from de */
 620         struct dirpiece *dp = dpaddr(block, pnum);
 621         dp->target = cpu_to_le32(de->target);
 622         dp->type = de->type;
 623 }
 624
 625 void lafs_dir_split(char *orig, int psz, char *new1, char *new2,
 626                     const char *name, u32 target, int type, u32 *newhash,
 627                     u32 seed, u32 hash, int chainoffset)
 628 {
 629         /* Split the orig block together with the new name, into new1 and new2.
 630          * Linearise orig, then copy one entry into which block is least empty
 631          * A hash somewhere between the two blocks is placed in *newhash.
 632          * It could be the highest in 'new1' but will be less than the
 633          * lowest in 'new2'
 634          *
 635          */
 636         struct dirheader *dh = (struct dirheader*)orig;
 637         struct dirheader *dh1 = (struct dirheader*)new1;
 638         struct dirheader *dh2 = (struct dirheader*)new2;
 639         struct dirpiece *dp;
 640         int first, last;
 641         int full1=0, full2=0;
 642         u32 offset, maxhash, minhash, hval;
 643
 644         dir_linearise(orig, psz);
 645
 646         first = dh->root;
 647         dp = dpaddr(orig, first);
 648         last = dp->next[0];
 649         if (first == 0 || last == 0)
 650                 /* orig was empty ?? */
 651                 BUG();
 652
 653         /* create new1 and new2 with first and last */
 654         hval = hash_piece(seed, dp, &offset);
 655         if (type &&  hash < hval) {
 656                 lafs_dir_init_block(new1, psz, name, 0, target, type,
 657                                     chainoffset);
 658                 type = 0;
 659                 maxhash = hash;
 660         } else {
 661                 lafs_dir_init_block(new1, psz, dp->name, dp->length,
 662                                     le32_to_cpu(dp->target), dp->type,
 663                                     offset);
 664                 maxhash = hval;
 665                 if (first == last)
 666                         first = 0;
 667                 else
 668                         first = dp->next[1];
 669         }
 670         dp = dpaddr(orig, last);
 671         hval = hash_piece(seed, dp, &offset);
 672         if (type && hash > hval) {
 673                 lafs_dir_init_block(new2, psz, name, 0, target, type,
 674                                     chainoffset);
 675                 minhash = hash;
 676                 type = 0;
 677         } else {
 678                 BUG_ON(!first);
 679                 lafs_dir_init_block(new2, psz, dp->name, dp->length,
 680                                     le32_to_cpu(dp->target), dp->type,
 681                                     offset);
 682                 minhash = hval;
 683                 if (first == last)
 684                         first = 0;
 685                 else
 686                         last = dp->next[0];
 687         }
 688
 689         while (first || type) {
 690                 /* everything from 'first' to 'last', plus 'name' (if type)
 691                  * is allowed to go in either block.
 692                  * Choose a block, and an entry, and insert it (if possible)
 693                  */
 694                 if (full2 || (dh1->freepieces >= dh2->freepieces && ! full1)) {
 695                         /* insert into new1 from first or name */
 696                         dp = dpaddr(orig, first);
 697                         if (first)
 698                                 hval = hash_piece(seed, dp, &offset);
 699                         if (type == 0 || (first && hval < hash)) {
 700                                 /* first is the preferred candidate */
 701                                 if (!lafs_dir_add_ent(new1, psz, dp->name,
 702                                                       dp->length,
 703                                                       le32_to_cpu(dp->target),
 704                                                       dp->type, seed, hval, offset))
 705                                         full1 = 1;
 706                                 else {
 707                                         maxhash = hval;
 708                                         if (first == last)
 709                                                 first = 0;
 710                                         else
 711                                                 first = dp->next[1];
 712                                 }
 713                         } else {
 714                                 /* insert name */
 715                                 if (!lafs_dir_add_ent(new1, psz, name, 0, target,
 716                                                       type, seed, hash, chainoffset))
 717                                         full1 = 1;
 718                                 else {
 719                                         maxhash = hash;
 720                                         type = 0;
 721                                 }
 722                         }
 723                 } else {
 724                         /* insert into new2 */
 725                         dp = dpaddr(orig, last);
 726                         if (first)
 727                                 hval = hash_piece(seed, dp, &offset);
 728                         if (type == 0 || (first && hval > hash )) {
 729                                 /* last is the preferred candidate */
 730                                 if (!lafs_dir_add_ent(new2, psz,
 731                                                       dp->name, dp->length,
 732                                                       le32_to_cpu(dp->target),
 733                                                       dp->type, seed, hval, offset))
 734                                         full2 = 1;
 735                                 else {
 736                                         minhash = hval;
 737                                         if (first == last)
 738                                                 first = 0;
 739                                         else
 740                                                 last = dp->next[0];
 741                                 }
 742                         } else {
 743                                 if (!lafs_dir_add_ent(new2, psz, name, 0,
 744                                                       target, type, seed,
 745                                                       hval, chainoffset))
 746                                         full2 = 1;
 747                                 else {
 748                                         minhash = hash;
 749                                         type = 0;
 750                                 }
 751                         }
 752                 }
 753         }
 754
 755         /* newhash could be minhash, but not
 756          * maxhash */
 757         *newhash = (minhash + maxhash) / 2;
 758 }
 759
 760 void lafs_dir_repack(char *block, int psz, char *new, u32 seed, int merge)
 761 {
 762         struct dirheader *dh = (struct dirheader*)block;
 763         int pnum = (sizeof(struct dirheader) + (1<<psz)-1)>>psz;
 764         int first = !merge;
 765
 766         while (pnum <= dh->lastpiece) {
 767                 int space;
 768                 struct dirpiece *dp = dpaddr(block, pnum);
 769
 770                 if (dp->target) {
 771                         u32 offset;
 772                         u32 hash = hash_piece(seed, dp, &offset);
 773                         if (first)
 774                                 lafs_dir_init_block(new, psz, dp->name,
 775                                                     dp->length,
 776                                                     le32_to_cpu(dp->target),
 777                                                     dp->type, offset);
 778                         else
 779                                 lafs_dir_add_ent(new, psz, dp->name, dp->length,
 780                                                  le32_to_cpu(dp->target),
 781                                                  dp->type, seed, hash, offset);
 782                         first = 0;
 783                 }
 784                 space = dp->length + (dp->chain_info < 2 ? 0 : dp->chain_info == 2 ? 1 : 4);
 785                 space += offsetof(struct dirpiece, name);
 786                 space = DIV_ROUND_UP(space, 1<<psz);
 787
 788                 pnum += space;
 789         }
 790 }
 791
 792 int lafs_dir_find(char *block, int psz, u32 seed, u32 hash, u8 *pp)
 793 {
 794         /* Find the entry for 'hash', if it exists.
 795          * Return 1 if found, 0 if not.
 796          * set 'pp' to the piece number if found, or the
 797          * next larger piece if not (zero if nothing is larger).
 798          */
 799         struct dirheader *dh = (struct dirheader*)block;
 800         int pnum = dh->root;
 801         int cnt = 256;
 802
 803         *pp = 0;
 804
 805         while (pnum && cnt) {
 806                 struct dirpiece *dp = dpaddr(block, pnum);
 807                 u32 hval = hash_piece(seed, dp, NULL);
 808
 809                 if (hval == hash) {
 810                         *pp = pnum;
 811                         return 1;
 812                 }
 813
 814                 if (hash > hval)
 815                         pnum = dp->next[1];
 816                 else {
 817                         *pp = pnum;
 818                         pnum = dp->next[0];
 819                 }
 820                 cnt --;
 821         }
 822         return 0;
 823 }
 824
 825 int dir_check_loop(char *block, int psz, int pnum, int depth)
 826 {
 827         /* walk around the tree, and BUG if we ever get a depth > 255 */
 828         struct dirheader *dh = (struct dirheader*)block;
 829
 830         if (pnum == -1)
 831                 pnum = dh->root;
 832         if (depth <= 0) return 1;
 833         if (pnum < 0 || pnum >= 256)
 834                 BUG();
 835
 836         if (pnum) {
 837                 struct dirpiece *dp = dpaddr(block, pnum);
 838                 if (dir_check_loop(block, psz, dp->next[0], depth-1) ||
 839                     dir_check_loop(block, psz, dp->next[1], depth-1)) {
 840                         printk(" ..%d(%d)\n", pnum, depth);
 841                         return 1;
 842                 }
 843         }
 844         return 0;
 845 }
 846
 847 int lafs_dir_empty(char *block)
 848 {
 849         struct dirheader *dh = (struct dirheader*)block;
 850         return dh->root == 0;
 851 }
 852
 853 int lafs_dir_blk_size(char *block, int psz)
 854 {
 855         /* how much of this block do we actually need to store */
 856         struct dirheader *dh = (struct dirheader*)block;
 857         if (lafs_dir_empty(block))
 858                 return 0;
 859         return (dh->lastpiece+1) << psz;
 860 }
 861
 862
 863
 864 /* Testing code here - no new important functionality */
 865 #ifndef MAIN
 866
 867 static void xprintk(char *block, int psz, char *s, int a, int b, int c, int d)
 868 {
 869         printk(s,a,b,c,d);
 870         dir_print(block, psz);
 871         BUG();
 872 }
 873
 874 static int dir_check_depth(char *block, int psz, int p)
 875 {
 876         struct dirpiece *dp = dpaddr(block,p);
 877         int b,f;
 878
 879         if (p == 0) return 0;
 880         b = dir_check_depth(block, psz, dp->next[0]);
 881         f = dir_check_depth(block, psz, dp->next[1]);
 882         if (b == f) {
 883                 if (dp->longer != Neither)
 884                         xprintk(block,psz, "... %d - b=%d f=%d lgr=%d\n", p, b, f, dp->longer);
 885                 return b+1;
 886         }
 887         if (b == f-1) {
 888                 if (dp->longer != 1)
 889                         xprintk(block,psz, "... %d - b=%d f=%d lgr=%d\n", p, b, f, dp->longer);
 890                 return f+1;
 891         }
 892         if (b-1 == f) {
 893                 if (dp->longer != 0)
 894                         xprintk(block,psz, "... %d - b=%d f=%d lgr=%d\n", p, b, f, dp->longer);
 895                 return b+1;
 896         }
 897         xprintk(block,psz, "... %d - b=%d f=%d lgr=%d\n", p, b, f, dp->longer);
 898         return (b>f?b:f)+1;
 899 }
 900
 901 static void dir_check_balance(char *block, int psz)
 902 {
 903         struct dirheader *dh = (struct dirheader*) block;
 904         dir_check_depth(block, psz, dh->root);
 905 }
 906
 907 static void dir_print_piece(char *block, int psz, int piece, int depth, int dir)
 908 {
 909         struct dirpiece *dp = dpaddr(block, piece);
 910
 911         if (piece == 0) return;
 912
 913         dir_print_piece(block, psz, dp->next[0], depth+1, 0);
 914         printk("%3d - %08lu:%02d %*s%c", piece, (unsigned long) le32_to_cpu(dp->target),
 915                depth,depth*2, "",
 916                dir?'\\':'/');
 917
 918         printk("%.*s\n", dp->length, dp->name);
 919         dir_print_piece(block, psz, dp->next[1], depth+1, 1);
 920 }
 921
 922 static void dir_print_block(char *block, int psz, int sort)
 923 {
 924         struct dirheader *dh;
 925         struct dirpiece *dp;
 926
 927         dh = (struct dirheader *)block;
 928         printk("===Directory Block===\n");
 929
 930         printk(" Root: %d\n", dh->root);
 931         printk(" Last Piece : %d (%d left)\n", dh->lastpiece, 255 - dh->lastpiece);
 932         printk(" Free Pieces: %d (%d deleted)\n", dh->freepieces, dh->freepieces - (255 - dh->lastpiece));
 933 /*
 934         if (dh->reserved)
 935                 printk( "!!!!!! Reserved is non-zero : %d\n", dh->reserved);
 936 */
 937         if (sort==1)
 938                 dir_print_piece(block, psz, dh->root, 0, 1);
 939         else if (sort == 2) {
 940                 /* linearised */
 941                 int pnum = dh->root;
 942                 while (pnum) {
 943                         dp = dpaddr(block, pnum);
 944                         printk("%3d - %08lu: (b:%-3d, f:%-3d, l:%d, type:%d  ",
 945                                pnum, (unsigned long) le32_to_cpu(dp->target),
 946                                dp->next[0], dp->next[1], dp->longer,
 947                                dp->type);
 948                         printk(": (%d)%.*s\n", dp->length, dp->length, dp->name);
 949                         pnum = dp->next[1];
 950                 }
 951         } else {
 952                 /* don't interpret the pieces too much */
 953                 int pnum = (sizeof(struct dirheader)+ (1<<psz)-1)>>psz;
 954                 while (pnum <= dh->lastpiece) {
 955                         dp = dpaddr(block, pnum);
 956                         printk("%3d - %08lu: (b:%-3d, f:%-3d, l:%d, type:%d  ",
 957                                pnum, (unsigned long)le32_to_cpu(dp->target),
 958                                dp->next[0], dp->next[1], dp->longer,
 959                                dp->type);
 960                         printk(": (%d)%.*s\n", dp->length, dp->length, dp->name);
 961                         pnum += (offsetof(struct dirpiece, name) + dp->length +(1<<psz)-1)>>psz;
 962                 }
 963         }
 964 }
 965 void dir_print(char *buf, int psz)
 966 {
 967         dir_print_block(buf, psz, 1);
 968 }
 969 #endif
 970
 971 #ifdef MAIN
 972
 973
 974 int noise = 0;
 975 int main(int argc, char **argv)
 976 {
 977         char block[4096];
 978         int blenshift = 10;
 979         int psz = blenshift - 8;
 980         int arg = 2;
 981         char nm[256];
 982
 983         lafs_dir_init_block(block, psz, argv[1], 0, 42, 3, 0);
 984         while (arg < argc-1) {
 985                 if (argv[arg][0] != '-')
 986                         switch(lafs_dir_add_ent(block, psz, argv[arg], 0, 42+arg, 4, 0)) {
 987                         case 0: printf("%s didn't fit!\n", argv[arg]); break;
 988                         case -1: printf("%s already exists\n", argv[arg]); break;
 989                         case 1: printf("%s inserted\n", argv[arg]);
 990                         }
 991                 else
 992                         switch (lafs_dir_del_ent(block, psz, argv[arg]+1, 0)) {
 993                         case 0: printf("%s not found!\n", argv[arg]); break;
 994                         case -2:printf("%s not deleted - bad dir\n", argv[arg]); break;
 995                         case 1: printf("%s deleted\n", argv[arg]); break;
 996                         }
 997
 998                 dir_check_balance(block, psz);
 999                 arg++;
1000         }
1001         dir_print_block(block, psz, 0);
1002         dir_print_block(block, psz, 1);
1003
1004         lafs_dir_split(block, psz, block+1024, block+2048, argv[arg], 40, 2, nm);
1005         dir_print_block(block+1024, psz, 1);
1006         dir_print_block(block+2048, psz, 1);
1007         dir_get_prefix(block+1024, block+2048, psz, block+3096);
1008         printf("Prefix is <%s>\n", block+3096);
1009         lafs_dir_repack(block+1024, psz, block, 0);
1010         lafs_dir_repack(block+2048, psz, block, 1);
1011         printf("============= repacked ===================\n");
1012         dir_print_block(block, psz, 1);
1013         exit(0);
1014 }
1015 #endif