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