dir-avl.c

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