upstream/illumos/illumos-gate: comparison usr/src/uts/common/fs/zfs/zap

equal deleted inserted replaced

-:71aba7712438
+:3047ad28a67b
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
 /*
-* Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
+* Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */
 #pragma ident	"%Z%%M%	%I%	%E% SMI"
 #include <sys/zap.h>
 #include <sys/zap_impl.h>
 #include <sys/zap_leaf.h>
 #include <sys/spa.h>
 #include <sys/dmu.h>
+static uint16_t *zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry);
 #define	CHAIN_END 0xffff /* end of the chunk chain */
 /* half the (current) minimum block size */
 #define	MAX_ARRAY_BYTES (8<<10)
 		}
 	}
 }
 void
-zap_leaf_init(zap_leaf_t *l)
+zap_leaf_init(zap_leaf_t *l, int version)
 {
 	int i;
 	l->l_bs = highbit(l->l_dbuf->db_size)-1;
 	zap_memset(&l->l_phys->l_hdr, 0, sizeof (struct zap_leaf_header));
 	}
 	ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)-1).l_free.lf_next = CHAIN_END;
 	l->l_phys->l_hdr.lh_block_type = ZBT_LEAF;
 	l->l_phys->l_hdr.lh_magic = ZAP_LEAF_MAGIC;
 	l->l_phys->l_hdr.lh_nfree = ZAP_LEAF_NUMCHUNKS(l);
+	if (version >= SPA_VERSION_NORMALIZATION)
+		l->l_phys->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
 }
 /*
 * Routines which manipulate leaf chunks (l_chunk[]).
 */
 }
 /*
 * Only to be used on 8-bit arrays.
 * array_len is actual len in bytes (not encoded le_value_length).
-* buf is null-terminated.
+* namenorm is null-terminated.
 */
-static int
+static boolean_t
-zap_leaf_array_equal(zap_leaf_t *l, int chunk,
+zap_leaf_array_match(zap_leaf_t *l, zap_name_t *zn, int chunk, int array_len)
-int array_len, const char *buf)
 {
 	int bseen = 0;
+	if (zn->zn_matchtype == MT_FIRST) {
+		char *thisname = kmem_alloc(array_len, KM_SLEEP);
+		boolean_t match;
+		zap_leaf_array_read(l, chunk, 1, array_len, 1,
+		    array_len, thisname);
+		match = zap_match(zn, thisname);
+		kmem_free(thisname, array_len);
+		return (match);
+	}
+	/* Fast path for exact matching */
 	while (bseen < array_len) {
 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
 		int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);
 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
-		if (bcmp(la->la_array, buf + bseen, toread))
+		if (bcmp(la->la_array, zn->zn_name_orij + bseen, toread))
 			break;
 		chunk = la->la_next;
 		bseen += toread;
 	}
 	return (bseen == array_len);
 /*
 * Routines which manipulate leaf entries.
 */
 int
-zap_leaf_lookup(zap_leaf_t *l,
+zap_leaf_lookup(zap_leaf_t *l, zap_name_t *zn, zap_entry_handle_t *zeh)
-const char *name, uint64_t h, zap_entry_handle_t *zeh)
 {
 	uint16_t *chunkp;
 	struct zap_leaf_entry *le;
 	ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
-	for (chunkp = LEAF_HASH_ENTPTR(l, h);
+again:
+	for (chunkp = LEAF_HASH_ENTPTR(l, zn->zn_hash);
 	    *chunkp != CHAIN_END; chunkp = &le->le_next) {
 		uint16_t chunk = *chunkp;
 		le = ZAP_LEAF_ENTRY(l, chunk);
 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
 		ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
-		if (le->le_hash != h)
+		if (le->le_hash != zn->zn_hash)
 			continue;
-		if (zap_leaf_array_equal(l, le->le_name_chunk,
+		/*
-		    le->le_name_length, name)) {
+		 * NB: the entry chain is always sorted by cd on
+		 * normalized zap objects, so this will find the
+		 * lowest-cd match for MT_FIRST.
+		 */
+		ASSERT(zn->zn_matchtype == MT_EXACT ||
+		    (l->l_phys->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED));
+		if (zap_leaf_array_match(l, zn, le->le_name_chunk,
+		    le->le_name_length)) {
 			zeh->zeh_num_integers = le->le_value_length;
 			zeh->zeh_integer_size = le->le_int_size;
 			zeh->zeh_cd = le->le_cd;
 			zeh->zeh_hash = le->le_hash;
 			zeh->zeh_chunkp = chunkp;
 			zeh->zeh_leaf = l;
 			return (0);
 		}
+	}
+	/*
+	 * NB: we could of course do this in one pass, but that would be
+	 * a pain.  We'll see if MT_BEST is even used much.
+	 */
+	if (zn->zn_matchtype == MT_BEST) {
+		zn->zn_matchtype = MT_FIRST;
+		goto again;
 	}
 	return (ENOENT);
 }
 	    ZAP_LEAF_ARRAY_NCHUNKS(valuelen);
 	if (numchunks > ZAP_LEAF_NUMCHUNKS(l))
 		return (E2BIG);
 	if (cd == ZAP_MAXCD) {
-		for (cd = 0; cd < ZAP_MAXCD; cd++) {
+		/* find the lowest unused cd */
+		if (l->l_phys->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED) {
+			cd = 0;
 			for (chunk = *LEAF_HASH_ENTPTR(l, h);
 			    chunk != CHAIN_END; chunk = le->le_next) {
 				le = ZAP_LEAF_ENTRY(l, chunk);
-				if (le->le_hash == h &&
+				if (le->le_cd > cd)
-				    le->le_cd == cd) {
 					break;
+				if (le->le_hash == h) {
+					ASSERT3U(cd, ==, le->le_cd);
+					cd++;
 				}
 			}
-			/* If this cd is not in use, we are good. */
+		} else {
-			if (chunk == CHAIN_END)
+			/* old unsorted format; do it the O(n^2) way */
-				break;
+			for (cd = 0; cd < ZAP_MAXCD; cd++) {
-		}
+				for (chunk = *LEAF_HASH_ENTPTR(l, h);
-		/* If we tried all the cd's, we lose. */
+				    chunk != CHAIN_END; chunk = le->le_next) {
-		if (cd == ZAP_MAXCD)
+					le = ZAP_LEAF_ENTRY(l, chunk);
-			return (ENOSPC);
+					if (le->le_hash == h &&
+					    le->le_cd == cd) {
+						break;
+					}
+				}
+				/* If this cd is not in use, we are good. */
+				if (chunk == CHAIN_END)
+					break;
+			}
+		}
+		/*
+		 * we would run out of space in a block before we could
+		 * have ZAP_MAXCD entries
+		 */
+		ASSERT3U(cd, <, ZAP_MAXCD);
 	}
 	if (l->l_phys->l_hdr.lh_nfree < numchunks)
 		return (EAGAIN);
 	le->le_int_size = integer_size;
 	le->le_hash = h;
 	le->le_cd = cd;
 	/* link it into the hash chain */
-	chunkp = LEAF_HASH_ENTPTR(l, h);
+	/* XXX if we did the search above, we could just use that */
-	le->le_next = *chunkp;
+	chunkp = zap_leaf_rehash_entry(l, chunk);
-	*chunkp = chunk;
 	l->l_phys->l_hdr.lh_nentries++;
 	zeh->zeh_leaf = l;
 	zeh->zeh_num_integers = num_integers;
 	return (0);
 }
 /*
+* Determine if there is another entry with the same normalized form.
+* For performance purposes, either zn or name must be provided (the
+* other can be NULL).  Note, there usually won't be any hash
+* conflicts, in which case we don't need the concatenated/normalized
+* form of the name.  But all callers have one of these on hand anyway,
+* so might as well take advantage.  A cleaner but slower interface
+* would accept neither argument, and compute the normalized name as
+* needed (using zap_name_alloc(zap_entry_read_name(zeh))).
+*/
+boolean_t
+zap_entry_normalization_conflict(zap_entry_handle_t *zeh, zap_name_t *zn,
+const char *name, zap_t *zap)
+{
+	uint64_t chunk;
+	struct zap_leaf_entry *le;
+	boolean_t allocdzn = B_FALSE;
+	if (zap->zap_normflags == 0)
+		return (B_FALSE);
+	for (chunk = *LEAF_HASH_ENTPTR(zeh->zeh_leaf, zeh->zeh_hash);
+	    chunk != CHAIN_END; chunk = le->le_next) {
+		le = ZAP_LEAF_ENTRY(zeh->zeh_leaf, chunk);
+		if (le->le_hash != zeh->zeh_hash)
+			continue;
+		if (le->le_cd == zeh->zeh_cd)
+			continue;
+		if (zn == NULL) {
+			zn = zap_name_alloc(zap, name, MT_FIRST);
+			allocdzn = B_TRUE;
+		}
+		if (zap_leaf_array_match(zeh->zeh_leaf, zn,
+		    le->le_name_chunk, le->le_name_length)) {
+			if (allocdzn)
+				zap_name_free(zn);
+			return (B_TRUE);
+		}
+	}
+	if (allocdzn)
+		zap_name_free(zn);
+	return (B_FALSE);
+}
+/*
 * Routines for transferring entries between leafs.
 */
-static void
+static uint16_t *
 zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
 {
 	struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, entry);
-	uint16_t *ptr = LEAF_HASH_ENTPTR(l, le->le_hash);
+	struct zap_leaf_entry *le2;
-	le->le_next = *ptr;
+	uint16_t *chunkp;
-	*ptr = entry;
+	/*
+	 * keep the entry chain sorted by cd
+	 * NB: this will not cause problems for unsorted leafs, though
+	 * it is unnecessary there.
+	 */
+	for (chunkp = LEAF_HASH_ENTPTR(l, le->le_hash);
+	    *chunkp != CHAIN_END; chunkp = &le2->le_next) {
+		le2 = ZAP_LEAF_ENTRY(l, *chunkp);
+		if (le2->le_cd > le->le_cd)
+			break;
+	}
+	le->le_next = *chunkp;
+	*chunkp = entry;
+	return (chunkp);
 }
 static uint16_t
 zap_leaf_transfer_array(zap_leaf_t *l, uint16_t chunk, zap_leaf_t *nl)
 {
 	chunk = zap_leaf_chunk_alloc(nl);
 	nle = ZAP_LEAF_ENTRY(nl, chunk);
 	*nle = *le; /* structure assignment */
-	zap_leaf_rehash_entry(nl, chunk);
+	(void) zap_leaf_rehash_entry(nl, chunk);
 	nle->le_name_chunk = zap_leaf_transfer_array(l, le->le_name_chunk, nl);
 	nle->le_value_chunk =
 	    zap_leaf_transfer_array(l, le->le_value_chunk, nl);
 /*
 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
 */
 void
-zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl)
+zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl, int version)
 {
 	int i;
 	int bit = 64 - 1 - l->l_phys->l_hdr.lh_prefix_len;
 	/* set new prefix and prefix_len */
 	nl->l_phys->l_hdr.lh_prefix = l->l_phys->l_hdr.lh_prefix | 1;
 	nl->l_phys->l_hdr.lh_prefix_len = l->l_phys->l_hdr.lh_prefix_len;
 	/* break existing hash chains */
 	zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
+	if (version >= SPA_VERSION_NORMALIZATION)
+		l->l_phys->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
 	/*
 	 * Transfer entries whose hash bit 'bit' is set to nl; rehash
 	 * the remaining entries
 	 *
 			continue;
 		if (le->le_hash & (1ULL << bit))
 			zap_leaf_transfer_entry(l, i, nl);
 		else
-			zap_leaf_rehash_entry(l, i);
+			(void) zap_leaf_rehash_entry(l, i);
 	}
 }
 void
 zap_leaf_stats(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)

changeset 5331	3047ad28a67b
parent 3052	7a3625b7393b
child 5498	334b476844ca