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