1724 lines · 51.7 KB · C
RawDownload
 	/* Firstly, we have to check the leaves in this node to see if there's	 * a matching one we should replace in place.	 */	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		ptr = node->slots[i];		if (!ptr) {			free_slot = i;			continue;		}		if (assoc_array_ptr_is_leaf(ptr) &&		    ops->compare_object(assoc_array_ptr_to_leaf(ptr),					index_key)) {			pr_devel("replace in slot %d\n", i);			edit->leaf_p = &node->slots[i];			edit->dead_leaf = node->slots[i];			pr_devel("<--%s() = ok [replace]\n", __func__);			return true;		}	} 	/* If there is a free slot in this node then we can just insert the	 * leaf here.	 */	if (free_slot >= 0) {		pr_devel("insert in free slot %d\n", free_slot);		edit->leaf_p = &node->slots[free_slot];		edit->adjust_count_on = node;		pr_devel("<--%s() = ok [insert]\n", __func__);		return true;	} 	/* The node has no spare slots - so we're either going to have to split	 * it or insert another node before it.	 *	 * Whatever, we're going to need at least two new nodes - so allocate	 * those now.  We may also need a new shortcut, but we deal with that	 * when we need it.	 */	new_n0 = kzalloc_obj(struct assoc_array_node);	if (!new_n0)		return false;	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);	new_n1 = kzalloc_obj(struct assoc_array_node);	if (!new_n1)		return false;	edit->new_meta[1] = assoc_array_node_to_ptr(new_n1); 	/* We need to find out how similar the leaves are. */	pr_devel("no spare slots\n");	have_meta = false;	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		ptr = node->slots[i];		if (assoc_array_ptr_is_meta(ptr)) {			edit->segment_cache[i] = 0xff;			have_meta = true;			continue;		}		base_seg = ops->get_object_key_chunk(			assoc_array_ptr_to_leaf(ptr), level);		base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;	} 	if (have_meta) {		pr_devel("have meta\n");		goto split_node;	} 	/* The node contains only leaves */	dissimilarity = 0;	base_seg = edit->segment_cache[0];	for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)		dissimilarity |= edit->segment_cache[i] ^ base_seg; 	pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity); 	if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {		/* The old leaves all cluster in the same slot.  We will need		 * to insert a shortcut if the new node wants to cluster with them.		 */		if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)			goto all_leaves_cluster_together; 		/* Otherwise all the old leaves cluster in the same slot, but		 * the new leaf wants to go into a different slot - so we		 * create a new node (n0) to hold the new leaf and a pointer to		 * a new node (n1) holding all the old leaves.		 *		 * This can be done by falling through to the node splitting		 * path.		 */		pr_devel("present leaves cluster but not new leaf\n");	} split_node:	pr_devel("split node\n"); 	/* We need to split the current node.  The node must contain anything	 * from a single leaf (in the one leaf case, this leaf will cluster	 * with the new leaf) and the rest meta-pointers, to all leaves, some	 * of which may cluster.	 *	 * It won't contain the case in which all the current leaves plus the	 * new leaves want to cluster in the same slot.	 *	 * We need to expel at least two leaves out of a set consisting of the	 * leaves in the node and the new leaf.  The current meta pointers can	 * just be copied as they shouldn't cluster with any of the leaves.	 *	 * We need a new node (n0) to replace the current one and a new node to	 * take the expelled nodes (n1).	 */	edit->set[0].to = assoc_array_node_to_ptr(new_n0);	new_n0->back_pointer = node->back_pointer;	new_n0->parent_slot = node->parent_slot;	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);	new_n1->parent_slot = -1; /* Need to calculate this */ do_split_node:	pr_devel("do_split_node\n"); 	new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;	new_n1->nr_leaves_on_branch = 0; 	/* Begin by finding two matching leaves.  There have to be at least two	 * that match - even if there are meta pointers - because any leaf that	 * would match a slot with a meta pointer in it must be somewhere	 * behind that meta pointer and cannot be here.  Further, given N	 * remaining leaf slots, we now have N+1 leaves to go in them.	 */	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		slot = edit->segment_cache[i];		if (slot != 0xff)			for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)				if (edit->segment_cache[j] == slot)					goto found_slot_for_multiple_occupancy;	}found_slot_for_multiple_occupancy:	pr_devel("same slot: %x %x [%02x]\n", i, j, slot);	BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);	BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);	BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT); 	new_n1->parent_slot = slot; 	/* Metadata pointers cannot change slot */	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)		if (assoc_array_ptr_is_meta(node->slots[i]))			new_n0->slots[i] = node->slots[i];		else			new_n0->slots[i] = NULL;	BUG_ON(new_n0->slots[slot] != NULL);	new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1); 	/* Filter the leaf pointers between the new nodes */	free_slot = -1;	next_slot = 0;	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		if (assoc_array_ptr_is_meta(node->slots[i]))			continue;		if (edit->segment_cache[i] == slot) {			new_n1->slots[next_slot++] = node->slots[i];			new_n1->nr_leaves_on_branch++;		} else {			do {				free_slot++;			} while (new_n0->slots[free_slot] != NULL);			new_n0->slots[free_slot] = node->slots[i];		}	} 	pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot); 	if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {		do {			free_slot++;		} while (new_n0->slots[free_slot] != NULL);		edit->leaf_p = &new_n0->slots[free_slot];		edit->adjust_count_on = new_n0;	} else {		edit->leaf_p = &new_n1->slots[next_slot++];		edit->adjust_count_on = new_n1;	} 	BUG_ON(next_slot <= 1); 	edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		if (edit->segment_cache[i] == 0xff) {			ptr = node->slots[i];			BUG_ON(assoc_array_ptr_is_leaf(ptr));			if (assoc_array_ptr_is_node(ptr)) {				side = assoc_array_ptr_to_node(ptr);				edit->set_backpointers[i] = &side->back_pointer;			} else {				shortcut = assoc_array_ptr_to_shortcut(ptr);				edit->set_backpointers[i] = &shortcut->back_pointer;			}		}	} 	ptr = node->back_pointer;	if (!ptr)		edit->set[0].ptr = &edit->array->root;	else if (assoc_array_ptr_is_node(ptr))		edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];	else		edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;	edit->excised_meta[0] = assoc_array_node_to_ptr(node);	pr_devel("<--%s() = ok [split node]\n", __func__);	return true; all_leaves_cluster_together:	/* All the leaves, new and old, want to cluster together in this node	 * in the same slot, so we have to replace this node with a shortcut to	 * skip over the identical parts of the key and then place a pair of	 * nodes, one inside the other, at the end of the shortcut and	 * distribute the keys between them.	 *	 * Firstly we need to work out where the leaves start diverging as a	 * bit position into their keys so that we know how big the shortcut	 * needs to be.	 *	 * We only need to make a single pass of N of the N+1 leaves because if	 * any keys differ between themselves at bit X then at least one of	 * them must also differ with the base key at bit X or before.	 */	pr_devel("all leaves cluster together\n");	diff = INT_MAX;	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]),					  index_key);		if (x < diff) {			BUG_ON(x < 0);			diff = x;		}	}	BUG_ON(diff == INT_MAX);	BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP); 	keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);	keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT; 	new_s0 = kzalloc_flex(*new_s0, index_key, keylen);	if (!new_s0)		return false;	edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0); 	edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);	new_s0->back_pointer = node->back_pointer;	new_s0->parent_slot = node->parent_slot;	new_s0->next_node = assoc_array_node_to_ptr(new_n0);	new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);	new_n0->parent_slot = 0;	new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);	new_n1->parent_slot = -1; /* Need to calculate this */ 	new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;	pr_devel("skip_to_level = %d [diff %d]\n", level, diff);	BUG_ON(level <= 0); 	for (i = 0; i < keylen; i++)		new_s0->index_key[i] =			ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE); 	if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) {		blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);		pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);		new_s0->index_key[keylen - 1] &= ~blank;	} 	/* This now reduces to a node splitting exercise for which we'll need	 * to regenerate the disparity table.	 */	for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {		ptr = node->slots[i];		base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr),						     level);		base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;		edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;	} 	base_seg = ops->get_key_chunk(index_key, level);	base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;	edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;	goto do_split_node;} /* * Handle insertion into the middle of a shortcut. */static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,					    const struct assoc_array_ops *ops,					    struct assoc_array_walk_result *result){	struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;	struct assoc_array_node *node, *new_n0, *side;	unsigned long sc_segments, dissimilarity, blank;	size_t keylen;	int level, sc_level, diff;	int sc_slot; 	shortcut	= result->wrong_shortcut.shortcut;	level		= result->wrong_shortcut.level;	sc_level	= result->wrong_shortcut.sc_level;	sc_segments	= result->wrong_shortcut.sc_segments;	dissimilarity	= result->wrong_shortcut.dissimilarity; 	pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",		 __func__, level, dissimilarity, sc_level); 	/* We need to split a shortcut and insert a node between the two	 * pieces.  Zero-length pieces will be dispensed with entirely.	 *	 * First of all, we need to find out in which level the first	 * difference was.	 */	diff = __ffs(dissimilarity);	diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;	diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;	pr_devel("diff=%d\n", diff); 	if (!shortcut->back_pointer) {		edit->set[0].ptr = &edit->array->root;	} else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {		node = assoc_array_ptr_to_node(shortcut->back_pointer);		edit->set[0].ptr = &node->slots[shortcut->parent_slot];	} else {		BUG();	} 	edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut); 	/* Create a new node now since we're going to need it anyway */	new_n0 = kzalloc_obj(struct assoc_array_node);	if (!new_n0)		return false;	edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);	edit->adjust_count_on = new_n0; 	/* Insert a new shortcut before the new node if this segment isn't of	 * zero length - otherwise we just connect the new node directly to the	 * parent.	 */	level += ASSOC_ARRAY_LEVEL_STEP;	if (diff > level) {		pr_devel("pre-shortcut %d...%d\n", level, diff);		keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);		keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT; 		new_s0 = kzalloc_flex(*new_s0, index_key, keylen);		if (!new_s0)			return false;		edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);		edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);		new_s0->back_pointer = shortcut->back_pointer;		new_s0->parent_slot = shortcut->parent_slot;		new_s0->next_node = assoc_array_node_to_ptr(new_n0);		new_s0->skip_to_level = diff; 		new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);		new_n0->parent_slot = 0; 		memcpy(new_s0->index_key, shortcut->index_key,		       flex_array_size(new_s0, index_key, keylen)); 		blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);		pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);		new_s0->index_key[keylen - 1] &= ~blank;	} else {		pr_devel("no pre-shortcut\n");		edit->set[0].to = assoc_array_node_to_ptr(new_n0);		new_n0->back_pointer = shortcut->back_pointer;		new_n0->parent_slot = shortcut->parent_slot;	} 	side = assoc_array_ptr_to_node(shortcut->next_node);	new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch; 	/* We need to know which slot in the new node is going to take a	 * metadata pointer.	 */	sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);	sc_slot &= ASSOC_ARRAY_FAN_MASK; 	pr_devel("new slot %lx >> %d -> %d\n",		 sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot); 	/* Determine whether we need to follow the new node with a replacement	 * for the current shortcut.  We could in theory reuse the current	 * shortcut if its parent slot number doesn't change - but that's a	 * 1-in-16 chance so not worth expending the code upon.	 */	level = diff + ASSOC_ARRAY_LEVEL_STEP;	if (level < shortcut->skip_to_level) {		pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);		keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);		keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT; 		new_s1 = kzalloc_flex(*new_s1, index_key, keylen);		if (!new_s1)			return false;		edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1); 		new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);		new_s1->parent_slot = sc_slot;		new_s1->next_node = shortcut->next_node;		new_s1->skip_to_level = shortcut->skip_to_level; 		new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1); 		memcpy(new_s1->index_key, shortcut->index_key,		       flex_array_size(new_s1, index_key, keylen)); 		edit->set[1].ptr = &side->back_pointer;		edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);	} else {		pr_devel("no post-shortcut\n"); 		/* We don't have to replace the pointed-to node as long as we		 * use memory barriers to make sure the parent slot number is		 * changed before the back pointer (the parent slot number is		 * irrelevant to the old parent shortcut).		 */		new_n0->slots[sc_slot] = shortcut->next_node;		edit->set_parent_slot[0].p = &side->parent_slot;		edit->set_parent_slot[0].to = sc_slot;		edit->set[1].ptr = &side->back_pointer;		edit->set[1].to = assoc_array_node_to_ptr(new_n0);	} 	/* Install the new leaf in a spare slot in the new node. */	if (sc_slot == 0)		edit->leaf_p = &new_n0->slots[1];	else		edit->leaf_p = &new_n0->slots[0]; 	pr_devel("<--%s() = ok [split shortcut]\n", __func__);	return true;} /** * assoc_array_insert - Script insertion of an object into an associative array * @array: The array to insert into. * @ops: The operations to use. * @index_key: The key to insert at. * @object: The object to insert. * * Precalculate and preallocate a script for the insertion or replacement of an * object in an associative array.  This results in an edit script that can * either be applied or cancelled. * * The function returns a pointer to an edit script or -ENOMEM. * * The caller should lock against other modifications and must continue to hold * the lock until assoc_array_apply_edit() has been called. * * Accesses to the tree may take place concurrently with this function, * provided they hold the RCU read lock. */struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,					    const struct assoc_array_ops *ops,					    const void *index_key,					    void *object){	struct assoc_array_walk_result result;	struct assoc_array_edit *edit; 	pr_devel("-->%s()\n", __func__); 	/* The leaf pointer we're given must not have the bottom bit set as we	 * use those for type-marking the pointer.  NULL pointers are also not	 * allowed as they indicate an empty slot but we have to allow them	 * here as they can be updated later.	 */	BUG_ON(assoc_array_ptr_is_meta(object)); 	edit = kzalloc_obj(struct assoc_array_edit);	if (!edit)		return ERR_PTR(-ENOMEM);	edit->array = array;	edit->ops = ops;	edit->leaf = assoc_array_leaf_to_ptr(object);	edit->adjust_count_by = 1; 	switch (assoc_array_walk(array, ops, index_key, &result)) {	case assoc_array_walk_tree_empty:		/* Allocate a root node if there isn't one yet */		if (!assoc_array_insert_in_empty_tree(edit))			goto enomem;		return edit; 	case assoc_array_walk_found_terminal_node:		/* We found a node that doesn't have a node/shortcut pointer in		 * the slot corresponding to the index key that we have to		 * follow.		 */		if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,							   &result))

Lines 501–1000 of 1724. Previous lines

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t