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