Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include <stdlib.h>
0003 #include <assert.h>
0004 #include <stdio.h>
0005 #include <string.h>
0006 
0007 #include <linux/slab.h>
0008 #include <linux/radix-tree.h>
0009 
0010 #include "test.h"
0011 
0012 
0013 static void
0014 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
0015 {
0016     unsigned long first = 0;
0017     int ret;
0018 
0019     item_check_absent(tree, index);
0020     assert(item_tag_get(tree, index, tag) == 0);
0021 
0022     item_insert(tree, index);
0023     assert(item_tag_get(tree, index, tag) == 0);
0024     item_tag_set(tree, index, tag);
0025     ret = item_tag_get(tree, index, tag);
0026     assert(ret != 0);
0027     ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag);
0028     assert(ret == 1);
0029     ret = item_tag_get(tree, index, !tag);
0030     assert(ret != 0);
0031     ret = item_delete(tree, index);
0032     assert(ret != 0);
0033     item_insert(tree, index);
0034     ret = item_tag_get(tree, index, tag);
0035     assert(ret == 0);
0036     ret = item_delete(tree, index);
0037     assert(ret != 0);
0038     ret = item_delete(tree, index);
0039     assert(ret == 0);
0040 }
0041 
0042 void simple_checks(void)
0043 {
0044     unsigned long index;
0045     RADIX_TREE(tree, GFP_KERNEL);
0046 
0047     for (index = 0; index < 10000; index++) {
0048         __simple_checks(&tree, index, 0);
0049         __simple_checks(&tree, index, 1);
0050     }
0051     verify_tag_consistency(&tree, 0);
0052     verify_tag_consistency(&tree, 1);
0053     printv(2, "before item_kill_tree: %d allocated\n", nr_allocated);
0054     item_kill_tree(&tree);
0055     rcu_barrier();
0056     printv(2, "after item_kill_tree: %d allocated\n", nr_allocated);
0057 }
0058 
0059 /*
0060  * Check that tags propagate correctly when extending a tree.
0061  */
0062 static void extend_checks(void)
0063 {
0064     RADIX_TREE(tree, GFP_KERNEL);
0065 
0066     item_insert(&tree, 43);
0067     assert(item_tag_get(&tree, 43, 0) == 0);
0068     item_tag_set(&tree, 43, 0);
0069     assert(item_tag_get(&tree, 43, 0) == 1);
0070     item_insert(&tree, 1000000);
0071     assert(item_tag_get(&tree, 43, 0) == 1);
0072 
0073     item_insert(&tree, 0);
0074     item_tag_set(&tree, 0, 0);
0075     item_delete(&tree, 1000000);
0076     assert(item_tag_get(&tree, 43, 0) != 0);
0077     item_delete(&tree, 43);
0078     assert(item_tag_get(&tree, 43, 0) == 0);    /* crash */
0079     assert(item_tag_get(&tree, 0, 0) == 1);
0080 
0081     verify_tag_consistency(&tree, 0);
0082 
0083     item_kill_tree(&tree);
0084 }
0085 
0086 /*
0087  * Check that tags propagate correctly when contracting a tree.
0088  */
0089 static void contract_checks(void)
0090 {
0091     struct item *item;
0092     int tmp;
0093     RADIX_TREE(tree, GFP_KERNEL);
0094 
0095     tmp = 1<<RADIX_TREE_MAP_SHIFT;
0096     item_insert(&tree, tmp);
0097     item_insert(&tree, tmp+1);
0098     item_tag_set(&tree, tmp, 0);
0099     item_tag_set(&tree, tmp, 1);
0100     item_tag_set(&tree, tmp+1, 0);
0101     item_delete(&tree, tmp+1);
0102     item_tag_clear(&tree, tmp, 1);
0103 
0104     assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
0105     assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);
0106 
0107     assert(item_tag_get(&tree, tmp, 0) == 1);
0108     assert(item_tag_get(&tree, tmp, 1) == 0);
0109 
0110     verify_tag_consistency(&tree, 0);
0111     item_kill_tree(&tree);
0112 }
0113 
0114 /*
0115  * Stupid tag thrasher
0116  *
0117  * Create a large linear array corresponding to the tree.   Each element in
0118  * the array is coherent with each node in the tree
0119  */
0120 
0121 enum {
0122     NODE_ABSENT = 0,
0123     NODE_PRESENT = 1,
0124     NODE_TAGGED = 2,
0125 };
0126 
0127 #define THRASH_SIZE     (1000 * 1000)
0128 #define N 127
0129 #define BATCH   33
0130 
0131 static void gang_check(struct radix_tree_root *tree,
0132             char *thrash_state, int tag)
0133 {
0134     struct item *items[BATCH];
0135     int nr_found;
0136     unsigned long index = 0;
0137     unsigned long last_index = 0;
0138 
0139     while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
0140                     index, BATCH, tag))) {
0141         int i;
0142 
0143         for (i = 0; i < nr_found; i++) {
0144             struct item *item = items[i];
0145 
0146             while (last_index < item->index) {
0147                 assert(thrash_state[last_index] != NODE_TAGGED);
0148                 last_index++;
0149             }
0150             assert(thrash_state[last_index] == NODE_TAGGED);
0151             last_index++;
0152         }
0153         index = items[nr_found - 1]->index + 1;
0154     }
0155 }
0156 
0157 static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
0158 {
0159     int insert_chunk;
0160     int delete_chunk;
0161     int tag_chunk;
0162     int untag_chunk;
0163     int total_tagged = 0;
0164     int total_present = 0;
0165 
0166     for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N)
0167     for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N)
0168     for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N)
0169     for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) {
0170         int i;
0171         unsigned long index;
0172         int nr_inserted = 0;
0173         int nr_deleted = 0;
0174         int nr_tagged = 0;
0175         int nr_untagged = 0;
0176         int actual_total_tagged;
0177         int actual_total_present;
0178 
0179         for (i = 0; i < insert_chunk; i++) {
0180             index = rand() % THRASH_SIZE;
0181             if (thrash_state[index] != NODE_ABSENT)
0182                 continue;
0183             item_check_absent(tree, index);
0184             item_insert(tree, index);
0185             assert(thrash_state[index] != NODE_PRESENT);
0186             thrash_state[index] = NODE_PRESENT;
0187             nr_inserted++;
0188             total_present++;
0189         }
0190 
0191         for (i = 0; i < delete_chunk; i++) {
0192             index = rand() % THRASH_SIZE;
0193             if (thrash_state[index] == NODE_ABSENT)
0194                 continue;
0195             item_check_present(tree, index);
0196             if (item_tag_get(tree, index, tag)) {
0197                 assert(thrash_state[index] == NODE_TAGGED);
0198                 total_tagged--;
0199             } else {
0200                 assert(thrash_state[index] == NODE_PRESENT);
0201             }
0202             item_delete(tree, index);
0203             assert(thrash_state[index] != NODE_ABSENT);
0204             thrash_state[index] = NODE_ABSENT;
0205             nr_deleted++;
0206             total_present--;
0207         }
0208 
0209         for (i = 0; i < tag_chunk; i++) {
0210             index = rand() % THRASH_SIZE;
0211             if (thrash_state[index] != NODE_PRESENT) {
0212                 if (item_lookup(tree, index))
0213                     assert(item_tag_get(tree, index, tag));
0214                 continue;
0215             }
0216             item_tag_set(tree, index, tag);
0217             item_tag_set(tree, index, tag);
0218             assert(thrash_state[index] != NODE_TAGGED);
0219             thrash_state[index] = NODE_TAGGED;
0220             nr_tagged++;
0221             total_tagged++;
0222         }
0223 
0224         for (i = 0; i < untag_chunk; i++) {
0225             index = rand() % THRASH_SIZE;
0226             if (thrash_state[index] != NODE_TAGGED)
0227                 continue;
0228             item_check_present(tree, index);
0229             assert(item_tag_get(tree, index, tag));
0230             item_tag_clear(tree, index, tag);
0231             item_tag_clear(tree, index, tag);
0232             assert(thrash_state[index] != NODE_PRESENT);
0233             thrash_state[index] = NODE_PRESENT;
0234             nr_untagged++;
0235             total_tagged--;
0236         }
0237 
0238         actual_total_tagged = 0;
0239         actual_total_present = 0;
0240         for (index = 0; index < THRASH_SIZE; index++) {
0241             switch (thrash_state[index]) {
0242             case NODE_ABSENT:
0243                 item_check_absent(tree, index);
0244                 break;
0245             case NODE_PRESENT:
0246                 item_check_present(tree, index);
0247                 assert(!item_tag_get(tree, index, tag));
0248                 actual_total_present++;
0249                 break;
0250             case NODE_TAGGED:
0251                 item_check_present(tree, index);
0252                 assert(item_tag_get(tree, index, tag));
0253                 actual_total_present++;
0254                 actual_total_tagged++;
0255                 break;
0256             }
0257         }
0258 
0259         gang_check(tree, thrash_state, tag);
0260 
0261         printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / "
0262                 "%d(%d) present, %d(%d) tagged\n",
0263             insert_chunk, nr_inserted,
0264             delete_chunk, nr_deleted,
0265             tag_chunk, nr_tagged,
0266             untag_chunk, nr_untagged,
0267             total_present, actual_total_present,
0268             total_tagged, actual_total_tagged);
0269     }
0270 }
0271 
0272 static void thrash_tags(void)
0273 {
0274     RADIX_TREE(tree, GFP_KERNEL);
0275     char *thrash_state;
0276 
0277     thrash_state = malloc(THRASH_SIZE);
0278     memset(thrash_state, 0, THRASH_SIZE);
0279 
0280     do_thrash(&tree, thrash_state, 0);
0281 
0282     verify_tag_consistency(&tree, 0);
0283     item_kill_tree(&tree);
0284     free(thrash_state);
0285 }
0286 
0287 static void leak_check(void)
0288 {
0289     RADIX_TREE(tree, GFP_KERNEL);
0290 
0291     item_insert(&tree, 1000000);
0292     item_delete(&tree, 1000000);
0293     item_kill_tree(&tree);
0294 }
0295 
0296 static void __leak_check(void)
0297 {
0298     RADIX_TREE(tree, GFP_KERNEL);
0299 
0300     printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
0301     item_insert(&tree, 1000000);
0302     printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
0303     item_delete(&tree, 1000000);
0304     printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
0305     item_kill_tree(&tree);
0306     printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
0307 }
0308 
0309 static void single_check(void)
0310 {
0311     struct item *items[BATCH];
0312     RADIX_TREE(tree, GFP_KERNEL);
0313     int ret;
0314     unsigned long first = 0;
0315 
0316     item_insert(&tree, 0);
0317     item_tag_set(&tree, 0, 0);
0318     ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
0319     assert(ret == 1);
0320     ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
0321     assert(ret == 0);
0322     verify_tag_consistency(&tree, 0);
0323     verify_tag_consistency(&tree, 1);
0324     ret = tag_tagged_items(&tree, first, 10, 10, XA_MARK_0, XA_MARK_1);
0325     assert(ret == 1);
0326     ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
0327     assert(ret == 1);
0328     item_tag_clear(&tree, 0, 0);
0329     ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
0330     assert(ret == 0);
0331     item_kill_tree(&tree);
0332 }
0333 
0334 void tag_check(void)
0335 {
0336     single_check();
0337     extend_checks();
0338     contract_checks();
0339     rcu_barrier();
0340     printv(2, "after extend_checks: %d allocated\n", nr_allocated);
0341     __leak_check();
0342     leak_check();
0343     rcu_barrier();
0344     printv(2, "after leak_check: %d allocated\n", nr_allocated);
0345     simple_checks();
0346     rcu_barrier();
0347     printv(2, "after simple_checks: %d allocated\n", nr_allocated);
0348     thrash_tags();
0349     rcu_barrier();
0350     printv(2, "after thrash_tags: %d allocated\n", nr_allocated);
0351 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!