radix-tree.c (f4b109c6dad54257eca837f9dd16a23f2eeab832) radix-tree.c (4d693d08607ab319095ec8942909df4b4aebdf66)
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter
5 * Copyright (C) 2006 Nick Piggin
6 * Copyright (C) 2012 Konstantin Khlebnikov
7 * Copyright (C) 2016 Intel, Matthew Wilcox
8 * Copyright (C) 2016 Intel, Ross Zwisler

--- 311 unchanged lines hidden (view full) ---

320 * must only free zeroed nodes into the slab. radix_tree_shrink
321 * can leave us with a non-NULL entry in the first slot, so clear
322 * that here to make sure.
323 */
324 for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
325 tag_clear(node, i, 0);
326
327 node->slots[0] = NULL;
1/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter
5 * Copyright (C) 2006 Nick Piggin
6 * Copyright (C) 2012 Konstantin Khlebnikov
7 * Copyright (C) 2016 Intel, Matthew Wilcox
8 * Copyright (C) 2016 Intel, Ross Zwisler

--- 311 unchanged lines hidden (view full) ---

320 * must only free zeroed nodes into the slab. radix_tree_shrink
321 * can leave us with a non-NULL entry in the first slot, so clear
322 * that here to make sure.
323 */
324 for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
325 tag_clear(node, i, 0);
326
327 node->slots[0] = NULL;
328 node->count = 0;
329
330 kmem_cache_free(radix_tree_node_cachep, node);
331}
332
333static inline void
334radix_tree_node_free(struct radix_tree_node *node)
335{
336 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);

--- 200 unchanged lines hidden (view full) ---

537out:
538 return maxshift + RADIX_TREE_MAP_SHIFT;
539}
540
541/**
542 * radix_tree_shrink - shrink radix tree to minimum height
543 * @root radix tree root
544 */
328
329 kmem_cache_free(radix_tree_node_cachep, node);
330}
331
332static inline void
333radix_tree_node_free(struct radix_tree_node *node)
334{
335 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);

--- 200 unchanged lines hidden (view full) ---

536out:
537 return maxshift + RADIX_TREE_MAP_SHIFT;
538}
539
540/**
541 * radix_tree_shrink - shrink radix tree to minimum height
542 * @root radix tree root
543 */
545static inline bool radix_tree_shrink(struct radix_tree_root *root)
544static inline bool radix_tree_shrink(struct radix_tree_root *root,
545 radix_tree_update_node_t update_node,
546 void *private)
546{
547 bool shrunk = false;
548
549 for (;;) {
550 struct radix_tree_node *node = root->rnode;
551 struct radix_tree_node *child;
552
553 if (!radix_tree_is_internal_node(node))

--- 38 unchanged lines hidden (view full) ---

592 * the page pointer, and if the page has 0 refcount it means it
593 * was concurrently deleted from pagecache so try the deref
594 * again. Fortunately there is already a requirement for logic
595 * to retry the entire slot lookup -- the indirect pointer
596 * problem (replacing direct root node with an indirect pointer
597 * also results in a stale slot). So tag the slot as indirect
598 * to force callers to retry.
599 */
547{
548 bool shrunk = false;
549
550 for (;;) {
551 struct radix_tree_node *node = root->rnode;
552 struct radix_tree_node *child;
553
554 if (!radix_tree_is_internal_node(node))

--- 38 unchanged lines hidden (view full) ---

593 * the page pointer, and if the page has 0 refcount it means it
594 * was concurrently deleted from pagecache so try the deref
595 * again. Fortunately there is already a requirement for logic
596 * to retry the entire slot lookup -- the indirect pointer
597 * problem (replacing direct root node with an indirect pointer
598 * also results in a stale slot). So tag the slot as indirect
599 * to force callers to retry.
600 */
600 if (!radix_tree_is_internal_node(child))
601 node->count = 0;
602 if (!radix_tree_is_internal_node(child)) {
601 node->slots[0] = RADIX_TREE_RETRY;
603 node->slots[0] = RADIX_TREE_RETRY;
604 if (update_node)
605 update_node(node, private);
606 }
602
603 radix_tree_node_free(node);
604 shrunk = true;
605 }
606
607 return shrunk;
608}
609
610static bool delete_node(struct radix_tree_root *root,
607
608 radix_tree_node_free(node);
609 shrunk = true;
610 }
611
612 return shrunk;
613}
614
615static bool delete_node(struct radix_tree_root *root,
611 struct radix_tree_node *node)
616 struct radix_tree_node *node,
617 radix_tree_update_node_t update_node, void *private)
612{
613 bool deleted = false;
614
615 do {
616 struct radix_tree_node *parent;
617
618 if (node->count) {
619 if (node == entry_to_node(root->rnode))
618{
619 bool deleted = false;
620
621 do {
622 struct radix_tree_node *parent;
623
624 if (node->count) {
625 if (node == entry_to_node(root->rnode))
620 deleted |= radix_tree_shrink(root);
626 deleted |= radix_tree_shrink(root, update_node,
627 private);
621 return deleted;
622 }
623
624 parent = node->parent;
625 if (parent) {
626 parent->slots[node->offset] = NULL;
627 parent->count--;
628 } else {

--- 246 unchanged lines hidden (view full) ---

875 node->exceptional += exceptional;
876 }
877
878 rcu_assign_pointer(*slot, item);
879}
880
881/**
882 * __radix_tree_replace - replace item in a slot
628 return deleted;
629 }
630
631 parent = node->parent;
632 if (parent) {
633 parent->slots[node->offset] = NULL;
634 parent->count--;
635 } else {

--- 246 unchanged lines hidden (view full) ---

882 node->exceptional += exceptional;
883 }
884
885 rcu_assign_pointer(*slot, item);
886}
887
888/**
889 * __radix_tree_replace - replace item in a slot
883 * @root: radix tree root
884 * @node: pointer to tree node
885 * @slot: pointer to slot in @node
886 * @item: new item to store in the slot.
890 * @root: radix tree root
891 * @node: pointer to tree node
892 * @slot: pointer to slot in @node
893 * @item: new item to store in the slot.
894 * @update_node: callback for changing leaf nodes
895 * @private: private data to pass to @update_node
887 *
888 * For use with __radix_tree_lookup(). Caller must hold tree write locked
889 * across slot lookup and replacement.
890 */
891void __radix_tree_replace(struct radix_tree_root *root,
892 struct radix_tree_node *node,
896 *
897 * For use with __radix_tree_lookup(). Caller must hold tree write locked
898 * across slot lookup and replacement.
899 */
900void __radix_tree_replace(struct radix_tree_root *root,
901 struct radix_tree_node *node,
893 void **slot, void *item)
902 void **slot, void *item,
903 radix_tree_update_node_t update_node, void *private)
894{
895 /*
896 * This function supports replacing exceptional entries and
897 * deleting entries, but that needs accounting against the
898 * node unless the slot is root->rnode.
899 */
900 replace_slot(root, node, slot, item,
901 !node && slot != (void **)&root->rnode);
902
904{
905 /*
906 * This function supports replacing exceptional entries and
907 * deleting entries, but that needs accounting against the
908 * node unless the slot is root->rnode.
909 */
910 replace_slot(root, node, slot, item,
911 !node && slot != (void **)&root->rnode);
912
903 delete_node(root, node);
913 if (!node)
914 return;
915
916 if (update_node)
917 update_node(node, private);
918
919 delete_node(root, node, update_node, private);
904}
905
906/**
907 * radix_tree_replace_slot - replace item in a slot
908 * @root: radix tree root
909 * @slot: pointer to slot
910 * @item: new item to store in the slot.
911 *

--- 668 unchanged lines hidden (view full) ---

1580 * rooted at @root, call this function to attempt freeing the
1581 * node and shrinking the tree.
1582 *
1583 * Returns %true if @node was freed, %false otherwise.
1584 */
1585bool __radix_tree_delete_node(struct radix_tree_root *root,
1586 struct radix_tree_node *node)
1587{
920}
921
922/**
923 * radix_tree_replace_slot - replace item in a slot
924 * @root: radix tree root
925 * @slot: pointer to slot
926 * @item: new item to store in the slot.
927 *

--- 668 unchanged lines hidden (view full) ---

1596 * rooted at @root, call this function to attempt freeing the
1597 * node and shrinking the tree.
1598 *
1599 * Returns %true if @node was freed, %false otherwise.
1600 */
1601bool __radix_tree_delete_node(struct radix_tree_root *root,
1602 struct radix_tree_node *node)
1603{
1588 return delete_node(root, node);
1604 return delete_node(root, node, NULL, NULL);
1589}
1590
1591static inline void delete_sibling_entries(struct radix_tree_node *node,
1592 void *ptr, unsigned offset)
1593{
1594#ifdef CONFIG_RADIX_TREE_MULTIORDER
1595 int i;
1596 for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {

--- 40 unchanged lines hidden (view full) ---

1637
1638 offset = get_slot_offset(node, slot);
1639
1640 /* Clear all tags associated with the item to be deleted. */
1641 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1642 node_tag_clear(root, node, tag, offset);
1643
1644 delete_sibling_entries(node, node_to_entry(slot), offset);
1605}
1606
1607static inline void delete_sibling_entries(struct radix_tree_node *node,
1608 void *ptr, unsigned offset)
1609{
1610#ifdef CONFIG_RADIX_TREE_MULTIORDER
1611 int i;
1612 for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {

--- 40 unchanged lines hidden (view full) ---

1653
1654 offset = get_slot_offset(node, slot);
1655
1656 /* Clear all tags associated with the item to be deleted. */
1657 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1658 node_tag_clear(root, node, tag, offset);
1659
1660 delete_sibling_entries(node, node_to_entry(slot), offset);
1645 __radix_tree_replace(root, node, slot, NULL);
1661 __radix_tree_replace(root, node, slot, NULL, NULL, NULL);
1646
1647 return entry;
1648}
1649EXPORT_SYMBOL(radix_tree_delete_item);
1650
1651/**
1652 * radix_tree_delete - delete an item from a radix tree
1653 * @root: radix tree root

--- 100 unchanged lines hidden --- 		1662
1663 return entry;
1664}
1665EXPORT_SYMBOL(radix_tree_delete_item);
1666
1667/**
1668 * radix_tree_delete - delete an item from a radix tree
1669 * @root: radix tree root

--- 100 unchanged lines hidden ---