sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zap_leaf.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #pragma ident   "%Z%%M% %I%     %E% SMI"
  27
  28 /*
  29  * The 512-byte leaf is broken into 32 16-byte chunks.
  30  * chunk number n means l_chunk[n], even though the header precedes it.
  31  * the names are stored null-terminated.
  32  */
  33
  34 #include <sys/zfs_context.h>
  35 #include <sys/zap.h>
  36 #include <sys/zap_impl.h>
  37 #include <sys/zap_leaf.h>
  38 #include <sys/spa.h>
  39 #include <sys/dmu.h>
  40
  41 #define CHAIN_END 0xffff /* end of the chunk chain */
  42
  43 /* half the (current) minimum block size */
  44 #define MAX_ARRAY_BYTES (8<<10)
  45
  46 #define LEAF_HASH(l, h) \
  47         ((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
  48         ((h) >> (64 - ZAP_LEAF_HASH_SHIFT(l)-(l)->l_phys->l_hdr.lh_prefix_len)))
  49
  50 #define LEAF_HASH_ENTPTR(l, h) (&(l)->l_phys->l_hash[LEAF_HASH(l, h)])
  51
  52
  53 static void
  54 zap_memset(void *a, int c, size_t n)
  55 {
  56         char *cp = a;
  57         char *cpend = cp + n;
  58
  59         while (cp < cpend)
  60                 *cp++ = c;
  61 }
  62
  63 static void
  64 stv(int len, void *addr, uint64_t value)
  65 {
  66         switch (len) {
  67         case 1:
  68                 *(uint8_t *)addr = value;
  69                 return;
  70         case 2:
  71                 *(uint16_t *)addr = value;
  72                 return;
  73         case 4:
  74                 *(uint32_t *)addr = value;
  75                 return;
  76         case 8:
  77                 *(uint64_t *)addr = value;
  78                 return;
  79         }
  80         ASSERT(!"bad int len");
  81 }
  82
  83 static uint64_t
  84 ldv(int len, const void *addr)
  85 {
  86         switch (len) {
  87         case 1:
  88                 return (*(uint8_t *)addr);
  89         case 2:
  90                 return (*(uint16_t *)addr);
  91         case 4:
  92                 return (*(uint32_t *)addr);
  93         case 8:
  94                 return (*(uint64_t *)addr);
  95         }
  96         ASSERT(!"bad int len");
  97         return (0xFEEDFACEDEADBEEFULL);
  98 }
  99
 100 void
 101 zap_leaf_byteswap(zap_leaf_phys_t *buf, int size)
 102 {
 103         int i;
 104         zap_leaf_t l;
 105         l.l_bs = highbit(size)-1;
 106         l.l_phys = buf;
 107
 108         buf->l_hdr.lh_block_type =      BSWAP_64(buf->l_hdr.lh_block_type);
 109         buf->l_hdr.lh_prefix =          BSWAP_64(buf->l_hdr.lh_prefix);
 110         buf->l_hdr.lh_magic =           BSWAP_32(buf->l_hdr.lh_magic);
 111         buf->l_hdr.lh_nfree =           BSWAP_16(buf->l_hdr.lh_nfree);
 112         buf->l_hdr.lh_nentries =        BSWAP_16(buf->l_hdr.lh_nentries);
 113         buf->l_hdr.lh_prefix_len =      BSWAP_16(buf->l_hdr.lh_prefix_len);
 114         buf->l_hdr.lh_freelist =        BSWAP_16(buf->l_hdr.lh_freelist);
 115
 116         for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(&l); i++)
 117                 buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);
 118
 119         for (i = 0; i < ZAP_LEAF_NUMCHUNKS(&l); i++) {
 120                 zap_leaf_chunk_t *lc = &ZAP_LEAF_CHUNK(&l, i);
 121                 struct zap_leaf_entry *le;
 122
 123                 switch (lc->l_free.lf_type) {
 124                 case ZAP_CHUNK_ENTRY:
 125                         le = &lc->l_entry;
 126
 127                         le->le_type =           BSWAP_8(le->le_type);
 128                         le->le_int_size =       BSWAP_8(le->le_int_size);
 129                         le->le_next =           BSWAP_16(le->le_next);
 130                         le->le_name_chunk =     BSWAP_16(le->le_name_chunk);
 131                         le->le_name_length =    BSWAP_16(le->le_name_length);
 132                         le->le_value_chunk =    BSWAP_16(le->le_value_chunk);
 133                         le->le_value_length =   BSWAP_16(le->le_value_length);
 134                         le->le_cd =             BSWAP_32(le->le_cd);
 135                         le->le_hash =           BSWAP_64(le->le_hash);
 136                         break;
 137                 case ZAP_CHUNK_FREE:
 138                         lc->l_free.lf_type =    BSWAP_8(lc->l_free.lf_type);
 139                         lc->l_free.lf_next =    BSWAP_16(lc->l_free.lf_next);
 140                         break;
 141                 case ZAP_CHUNK_ARRAY:
 142                         lc->l_array.la_type =   BSWAP_8(lc->l_array.la_type);
 143                         lc->l_array.la_next =   BSWAP_16(lc->l_array.la_next);
 144                         /* la_array doesn't need swapping */
 145                         break;
 146                 default:
 147                         ASSERT(!"bad leaf type");
 148                 }
 149         }
 150 }
 151
 152 void
 153 zap_leaf_init(zap_leaf_t *l)
 154 {
 155         int i;
 156
 157         l->l_bs = highbit(l->l_dbuf->db_size)-1;
 158         zap_memset(&l->l_phys->l_hdr, 0, sizeof (struct zap_leaf_header));
 159         zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
 160         for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
 161                 ZAP_LEAF_CHUNK(l, i).l_free.lf_type = ZAP_CHUNK_FREE;
 162                 ZAP_LEAF_CHUNK(l, i).l_free.lf_next = i+1;
 163         }
 164         ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)-1).l_free.lf_next = CHAIN_END;
 165         l->l_phys->l_hdr.lh_block_type = ZBT_LEAF;
 166         l->l_phys->l_hdr.lh_magic = ZAP_LEAF_MAGIC;
 167         l->l_phys->l_hdr.lh_nfree = ZAP_LEAF_NUMCHUNKS(l);
 168 }
 169
 170 /*
 171  * Routines which manipulate leaf chunks (l_chunk[]).
 172  */
 173
 174 static uint16_t
 175 zap_leaf_chunk_alloc(zap_leaf_t *l)
 176 {
 177         int chunk;
 178
 179         ASSERT(l->l_phys->l_hdr.lh_nfree > 0);
 180
 181         chunk = l->l_phys->l_hdr.lh_freelist;
 182         ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 183         ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_free.lf_type, ==, ZAP_CHUNK_FREE);
 184
 185         l->l_phys->l_hdr.lh_freelist = ZAP_LEAF_CHUNK(l, chunk).l_free.lf_next;
 186
 187         l->l_phys->l_hdr.lh_nfree--;
 188
 189         return (chunk);
 190 }
 191
 192 static void
 193 zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)
 194 {
 195         struct zap_leaf_free *zlf = &ZAP_LEAF_CHUNK(l, chunk).l_free;
 196         ASSERT3U(l->l_phys->l_hdr.lh_nfree, <, ZAP_LEAF_NUMCHUNKS(l));
 197         ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 198         ASSERT(zlf->lf_type != ZAP_CHUNK_FREE);
 199
 200         zlf->lf_type = ZAP_CHUNK_FREE;
 201         zlf->lf_next = l->l_phys->l_hdr.lh_freelist;
 202         bzero(zlf->lf_pad, sizeof (zlf->lf_pad)); /* help it to compress */
 203         l->l_phys->l_hdr.lh_freelist = chunk;
 204
 205         l->l_phys->l_hdr.lh_nfree++;
 206 }
 207
 208 /*
 209  * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
 210  */
 211
 212 static uint16_t
 213 zap_leaf_array_create(zap_leaf_t *l, const char *buf,
 214         int integer_size, int num_integers)
 215 {
 216         uint16_t chunk_head;
 217         uint16_t *chunkp = &chunk_head;
 218         int byten = 0;
 219         uint64_t value;
 220         int shift = (integer_size-1)*8;
 221         int len = num_integers;
 222
 223         ASSERT3U(num_integers * integer_size, <, MAX_ARRAY_BYTES);
 224
 225         while (len > 0) {
 226                 uint16_t chunk = zap_leaf_chunk_alloc(l);
 227                 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
 228                 int i;
 229
 230                 la->la_type = ZAP_CHUNK_ARRAY;
 231                 for (i = 0; i < ZAP_LEAF_ARRAY_BYTES; i++) {
 232                         if (byten == 0)
 233                                 value = ldv(integer_size, buf);
 234                         la->la_array[i] = value >> shift;
 235                         value <<= 8;
 236                         if (++byten == integer_size) {
 237                                 byten = 0;
 238                                 buf += integer_size;
 239                                 if (--len == 0)
 240                                         break;
 241                         }
 242                 }
 243
 244                 *chunkp = chunk;
 245                 chunkp = &la->la_next;
 246         }
 247         *chunkp = CHAIN_END;
 248
 249         return (chunk_head);
 250 }
 251
 252 static void
 253 zap_leaf_array_free(zap_leaf_t *l, uint16_t *chunkp)
 254 {
 255         uint16_t chunk = *chunkp;
 256
 257         *chunkp = CHAIN_END;
 258
 259         while (chunk != CHAIN_END) {
 260                 int nextchunk = ZAP_LEAF_CHUNK(l, chunk).l_array.la_next;
 261                 ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_array.la_type, ==,
 262                     ZAP_CHUNK_ARRAY);
 263                 zap_leaf_chunk_free(l, chunk);
 264                 chunk = nextchunk;
 265         }
 266 }
 267
 268 /* array_len and buf_len are in integers, not bytes */
 269 static void
 270 zap_leaf_array_read(zap_leaf_t *l, uint16_t chunk,
 271     int array_int_len, int array_len, int buf_int_len, uint64_t buf_len,
 272     char *buf)
 273 {
 274         int len = MIN(array_len, buf_len);
 275         int byten = 0;
 276         uint64_t value = 0;
 277
 278         ASSERT3U(array_int_len, <=, buf_int_len);
 279
 280         /* Fast path for one 8-byte integer */
 281         if (array_int_len == 8 && buf_int_len == 8 && len == 1) {
 282                 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
 283                 uint8_t *ip = la->la_array;
 284                 uint64_t *buf64 = (uint64_t *)buf;
 285
 286                 *buf64 = (uint64_t)ip[0] << 56 | (uint64_t)ip[1] << 48 |
 287                     (uint64_t)ip[2] << 40 | (uint64_t)ip[3] << 32 |
 288                     (uint64_t)ip[4] << 24 | (uint64_t)ip[5] << 16 |
 289                     (uint64_t)ip[6] << 8 | (uint64_t)ip[7];
 290                 return;
 291         }
 292
 293         /* Fast path for an array of 1-byte integers (eg. the entry name) */
 294         if (array_int_len == 1 && buf_int_len == 1 &&
 295             buf_len > array_len + ZAP_LEAF_ARRAY_BYTES) {
 296                 while (chunk != CHAIN_END) {
 297                         struct zap_leaf_array *la =
 298                             &ZAP_LEAF_CHUNK(l, chunk).l_array;
 299                         bcopy(la->la_array, buf, ZAP_LEAF_ARRAY_BYTES);
 300                         buf += ZAP_LEAF_ARRAY_BYTES;
 301                         chunk = la->la_next;
 302                 }
 303                 return;
 304         }
 305
 306         while (len > 0) {
 307                 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
 308                 int i;
 309
 310                 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 311                 for (i = 0; i < ZAP_LEAF_ARRAY_BYTES && len > 0; i++) {
 312                         value = (value << 8) | la->la_array[i];
 313                         byten++;
 314                         if (byten == array_int_len) {
 315                                 stv(buf_int_len, buf, value);
 316                                 byten = 0;
 317                                 len--;
 318                                 if (len == 0)
 319                                         return;
 320                                 buf += buf_int_len;
 321                         }
 322                 }
 323                 chunk = la->la_next;
 324         }
 325 }
 326
 327 /*
 328  * Only to be used on 8-bit arrays.
 329  * array_len is actual len in bytes (not encoded le_value_length).
 330  * buf is null-terminated.
 331  */
 332 static int
 333 zap_leaf_array_equal(zap_leaf_t *l, int chunk,
 334     int array_len, const char *buf)
 335 {
 336         int bseen = 0;
 337
 338         while (bseen < array_len) {
 339                 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
 340                 int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);
 341                 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 342                 if (bcmp(la->la_array, buf + bseen, toread))
 343                         break;
 344                 chunk = la->la_next;
 345                 bseen += toread;
 346         }
 347         return (bseen == array_len);
 348 }
 349
 350 /*
 351  * Routines which manipulate leaf entries.
 352  */
 353
 354 int
 355 zap_leaf_lookup(zap_leaf_t *l,
 356     const char *name, uint64_t h, zap_entry_handle_t *zeh)
 357 {
 358         uint16_t *chunkp;
 359         struct zap_leaf_entry *le;
 360
 361         ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
 362
 363         for (chunkp = LEAF_HASH_ENTPTR(l, h);
 364             *chunkp != CHAIN_END; chunkp = &le->le_next) {
 365                 uint16_t chunk = *chunkp;
 366                 le = ZAP_LEAF_ENTRY(l, chunk);
 367
 368                 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 369                 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
 370
 371                 if (le->le_hash != h)
 372                         continue;
 373
 374                 if (zap_leaf_array_equal(l, le->le_name_chunk,
 375                     le->le_name_length, name)) {
 376                         zeh->zeh_num_integers = le->le_value_length;
 377                         zeh->zeh_integer_size = le->le_int_size;
 378                         zeh->zeh_cd = le->le_cd;
 379                         zeh->zeh_hash = le->le_hash;
 380                         zeh->zeh_chunkp = chunkp;
 381                         zeh->zeh_leaf = l;
 382                         return (0);
 383                 }
 384         }
 385
 386         return (ENOENT);
 387 }
 388
 389 /* Return (h1,cd1 >= h2,cd2) */
 390 #define HCD_GTEQ(h1, cd1, h2, cd2) \
 391         ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
 392
 393 int
 394 zap_leaf_lookup_closest(zap_leaf_t *l,
 395     uint64_t h, uint32_t cd, zap_entry_handle_t *zeh)
 396 {
 397         uint16_t chunk;
 398         uint64_t besth = -1ULL;
 399         uint32_t bestcd = ZAP_MAXCD;
 400         uint16_t bestlh = ZAP_LEAF_HASH_NUMENTRIES(l)-1;
 401         uint16_t lh;
 402         struct zap_leaf_entry *le;
 403
 404         ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
 405
 406         for (lh = LEAF_HASH(l, h); lh <= bestlh; lh++) {
 407                 for (chunk = l->l_phys->l_hash[lh];
 408                     chunk != CHAIN_END; chunk = le->le_next) {
 409                         le = ZAP_LEAF_ENTRY(l, chunk);
 410
 411                         ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 412                         ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
 413
 414                         if (HCD_GTEQ(le->le_hash, le->le_cd, h, cd) &&
 415                             HCD_GTEQ(besth, bestcd, le->le_hash, le->le_cd)) {
 416                                 ASSERT3U(bestlh, >=, lh);
 417                                 bestlh = lh;
 418                                 besth = le->le_hash;
 419                                 bestcd = le->le_cd;
 420
 421                                 zeh->zeh_num_integers = le->le_value_length;
 422                                 zeh->zeh_integer_size = le->le_int_size;
 423                                 zeh->zeh_cd = le->le_cd;
 424                                 zeh->zeh_hash = le->le_hash;
 425                                 zeh->zeh_fakechunk = chunk;
 426                                 zeh->zeh_chunkp = &zeh->zeh_fakechunk;
 427                                 zeh->zeh_leaf = l;
 428                         }
 429                 }
 430         }
 431
 432         return (bestcd == ZAP_MAXCD ? ENOENT : 0);
 433 }
 434
 435 int
 436 zap_entry_read(const zap_entry_handle_t *zeh,
 437     uint8_t integer_size, uint64_t num_integers, void *buf)
 438 {
 439         struct zap_leaf_entry *le =
 440             ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
 441         ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
 442
 443         if (le->le_int_size > integer_size)
 444                 return (EINVAL);
 445
 446         zap_leaf_array_read(zeh->zeh_leaf, le->le_value_chunk, le->le_int_size,
 447             le->le_value_length, integer_size, num_integers, buf);
 448
 449         if (zeh->zeh_num_integers > num_integers)
 450                 return (EOVERFLOW);
 451         return (0);
 452
 453 }
 454
 455 int
 456 zap_entry_read_name(const zap_entry_handle_t *zeh, uint16_t buflen, char *buf)
 457 {
 458         struct zap_leaf_entry *le =
 459             ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
 460         ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
 461
 462         zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 1,
 463             le->le_name_length, 1, buflen, buf);
 464         if (le->le_name_length > buflen)
 465                 return (EOVERFLOW);
 466         return (0);
 467 }
 468
 469 int
 470 zap_entry_update(zap_entry_handle_t *zeh,
 471         uint8_t integer_size, uint64_t num_integers, const void *buf)
 472 {
 473         int delta_chunks;
 474         zap_leaf_t *l = zeh->zeh_leaf;
 475         struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, *zeh->zeh_chunkp);
 476
 477         delta_chunks = ZAP_LEAF_ARRAY_NCHUNKS(num_integers * integer_size) -
 478             ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_length * le->le_int_size);
 479
 480         if ((int)l->l_phys->l_hdr.lh_nfree < delta_chunks)
 481                 return (EAGAIN);
 482
 483         /*
 484          * We should search other chained leaves (via
 485          * zap_entry_remove,create?) otherwise returning EAGAIN will
 486          * just send us into an infinite loop if we have to chain
 487          * another leaf block, rather than being able to split this
 488          * block.
 489          */
 490
 491         zap_leaf_array_free(l, &le->le_value_chunk);
 492         le->le_value_chunk =
 493             zap_leaf_array_create(l, buf, integer_size, num_integers);
 494         le->le_value_length = num_integers;
 495         le->le_int_size = integer_size;
 496         return (0);
 497 }
 498
 499 void
 500 zap_entry_remove(zap_entry_handle_t *zeh)
 501 {
 502         uint16_t entry_chunk;
 503         struct zap_leaf_entry *le;
 504         zap_leaf_t *l = zeh->zeh_leaf;
 505
 506         ASSERT3P(zeh->zeh_chunkp, !=, &zeh->zeh_fakechunk);
 507
 508         entry_chunk = *zeh->zeh_chunkp;
 509         le = ZAP_LEAF_ENTRY(l, entry_chunk);
 510         ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
 511
 512         zap_leaf_array_free(l, &le->le_name_chunk);
 513         zap_leaf_array_free(l, &le->le_value_chunk);
 514
 515         *zeh->zeh_chunkp = le->le_next;
 516         zap_leaf_chunk_free(l, entry_chunk);
 517
 518         l->l_phys->l_hdr.lh_nentries--;
 519 }
 520
 521 int
 522 zap_entry_create(zap_leaf_t *l, const char *name, uint64_t h, uint32_t cd,
 523     uint8_t integer_size, uint64_t num_integers, const void *buf,
 524     zap_entry_handle_t *zeh)
 525 {
 526         uint16_t chunk;
 527         uint16_t *chunkp;
 528         struct zap_leaf_entry *le;
 529         uint64_t namelen, valuelen;
 530         int numchunks;
 531
 532         valuelen = integer_size * num_integers;
 533         namelen = strlen(name) + 1;
 534         ASSERT(namelen >= 2);
 535
 536         numchunks = 1 + ZAP_LEAF_ARRAY_NCHUNKS(namelen) +
 537             ZAP_LEAF_ARRAY_NCHUNKS(valuelen);
 538         if (numchunks > ZAP_LEAF_NUMCHUNKS(l))
 539                 return (E2BIG);
 540
 541         if (cd == ZAP_MAXCD) {
 542                 for (cd = 0; cd < ZAP_MAXCD; cd++) {
 543                         for (chunk = *LEAF_HASH_ENTPTR(l, h);
 544                             chunk != CHAIN_END; chunk = le->le_next) {
 545                                 le = ZAP_LEAF_ENTRY(l, chunk);
 546                                 if (le->le_hash == h &&
 547                                     le->le_cd == cd) {
 548                                         break;
 549                                 }
 550                         }
 551                         /* If this cd is not in use, we are good. */
 552                         if (chunk == CHAIN_END)
 553                                 break;
 554                 }
 555                 /* If we tried all the cd's, we lose. */
 556                 if (cd == ZAP_MAXCD)
 557                         return (ENOSPC);
 558         }
 559
 560         if (l->l_phys->l_hdr.lh_nfree < numchunks)
 561                 return (EAGAIN);
 562
 563         /* make the entry */
 564         chunk = zap_leaf_chunk_alloc(l);
 565         le = ZAP_LEAF_ENTRY(l, chunk);
 566         le->le_type = ZAP_CHUNK_ENTRY;
 567         le->le_name_chunk = zap_leaf_array_create(l, name, 1, namelen);
 568         le->le_name_length = namelen;
 569         le->le_value_chunk =
 570             zap_leaf_array_create(l, buf, integer_size, num_integers);
 571         le->le_value_length = num_integers;
 572         le->le_int_size = integer_size;
 573         le->le_hash = h;
 574         le->le_cd = cd;
 575
 576         /* link it into the hash chain */
 577         chunkp = LEAF_HASH_ENTPTR(l, h);
 578         le->le_next = *chunkp;
 579         *chunkp = chunk;
 580
 581         l->l_phys->l_hdr.lh_nentries++;
 582
 583         zeh->zeh_leaf = l;
 584         zeh->zeh_num_integers = num_integers;
 585         zeh->zeh_integer_size = le->le_int_size;
 586         zeh->zeh_cd = le->le_cd;
 587         zeh->zeh_hash = le->le_hash;
 588         zeh->zeh_chunkp = chunkp;
 589
 590         return (0);
 591 }
 592
 593 /*
 594  * Routines for transferring entries between leafs.
 595  */
 596
 597 static void
 598 zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
 599 {
 600         struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, entry);
 601         uint16_t *ptr = LEAF_HASH_ENTPTR(l, le->le_hash);
 602         le->le_next = *ptr;
 603         *ptr = entry;
 604 }
 605
 606 static uint16_t
 607 zap_leaf_transfer_array(zap_leaf_t *l, uint16_t chunk, zap_leaf_t *nl)
 608 {
 609         uint16_t new_chunk;
 610         uint16_t *nchunkp = &new_chunk;
 611
 612         while (chunk != CHAIN_END) {
 613                 uint16_t nchunk = zap_leaf_chunk_alloc(nl);
 614                 struct zap_leaf_array *nla =
 615                     &ZAP_LEAF_CHUNK(nl, nchunk).l_array;
 616                 struct zap_leaf_array *la =
 617                     &ZAP_LEAF_CHUNK(l, chunk).l_array;
 618                 int nextchunk = la->la_next;
 619
 620                 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 621                 ASSERT3U(nchunk, <, ZAP_LEAF_NUMCHUNKS(l));
 622
 623                 *nla = *la; /* structure assignment */
 624
 625                 zap_leaf_chunk_free(l, chunk);
 626                 chunk = nextchunk;
 627                 *nchunkp = nchunk;
 628                 nchunkp = &nla->la_next;
 629         }
 630         *nchunkp = CHAIN_END;
 631         return (new_chunk);
 632 }
 633
 634 static void
 635 zap_leaf_transfer_entry(zap_leaf_t *l, int entry, zap_leaf_t *nl)
 636 {
 637         struct zap_leaf_entry *le, *nle;
 638         uint16_t chunk;
 639
 640         le = ZAP_LEAF_ENTRY(l, entry);
 641         ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
 642
 643         chunk = zap_leaf_chunk_alloc(nl);
 644         nle = ZAP_LEAF_ENTRY(nl, chunk);
 645         *nle = *le; /* structure assignment */
 646
 647         zap_leaf_rehash_entry(nl, chunk);
 648
 649         nle->le_name_chunk = zap_leaf_transfer_array(l, le->le_name_chunk, nl);
 650         nle->le_value_chunk =
 651             zap_leaf_transfer_array(l, le->le_value_chunk, nl);
 652
 653         zap_leaf_chunk_free(l, entry);
 654
 655         l->l_phys->l_hdr.lh_nentries--;
 656         nl->l_phys->l_hdr.lh_nentries++;
 657 }
 658
 659 /*
 660  * Transfer the entries whose hash prefix ends in 1 to the new leaf.
 661  */
 662 void
 663 zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl)
 664 {
 665         int i;
 666         int bit = 64 - 1 - l->l_phys->l_hdr.lh_prefix_len;
 667
 668         /* set new prefix and prefix_len */
 669         l->l_phys->l_hdr.lh_prefix <<= 1;
 670         l->l_phys->l_hdr.lh_prefix_len++;
 671         nl->l_phys->l_hdr.lh_prefix = l->l_phys->l_hdr.lh_prefix | 1;
 672         nl->l_phys->l_hdr.lh_prefix_len = l->l_phys->l_hdr.lh_prefix_len;
 673
 674         /* break existing hash chains */
 675         zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
 676
 677         /*
 678          * Transfer entries whose hash bit 'bit' is set to nl; rehash
 679          * the remaining entries
 680          *
 681          * NB: We could find entries via the hashtable instead. That
 682          * would be O(hashents+numents) rather than O(numblks+numents),
 683          * but this accesses memory more sequentially, and when we're
 684          * called, the block is usually pretty full.
 685          */
 686         for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
 687                 struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, i);
 688                 if (le->le_type != ZAP_CHUNK_ENTRY)
 689                         continue;
 690
 691                 if (le->le_hash & (1ULL << bit))
 692                         zap_leaf_transfer_entry(l, i, nl);
 693                 else
 694                         zap_leaf_rehash_entry(l, i);
 695         }
 696 }
 697
 698 void
 699 zap_leaf_stats(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)
 700 {
 701         int i, n;
 702
 703         n = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift -
 704             l->l_phys->l_hdr.lh_prefix_len;
 705         n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
 706         zs->zs_leafs_with_2n_pointers[n]++;
 707
 708
 709         n = l->l_phys->l_hdr.lh_nentries/5;
 710         n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
 711         zs->zs_blocks_with_n5_entries[n]++;
 712
 713         n = ((1<<FZAP_BLOCK_SHIFT(zap)) -
 714             l->l_phys->l_hdr.lh_nfree * (ZAP_LEAF_ARRAY_BYTES+1))*10 /
 715             (1<<FZAP_BLOCK_SHIFT(zap));
 716         n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
 717         zs->zs_blocks_n_tenths_full[n]++;
 718
 719         for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(l); i++) {
 720                 int nentries = 0;
 721                 int chunk = l->l_phys->l_hash[i];
 722
 723                 while (chunk != CHAIN_END) {
 724                         struct zap_leaf_entry *le =
 725                             ZAP_LEAF_ENTRY(l, chunk);
 726
 727                         n = 1 + ZAP_LEAF_ARRAY_NCHUNKS(le->le_name_length) +
 728                             ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_length *
 729                                 le->le_int_size);
 730                         n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
 731                         zs->zs_entries_using_n_chunks[n]++;
 732
 733                         chunk = le->le_next;
 734                         nentries++;
 735                 }
 736
 737                 n = nentries;
 738                 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
 739                 zs->zs_buckets_with_n_entries[n]++;
 740         }
 741 }