Eric Lee / smarc-fsl-linux-kernel

Blame view

lib/test_ida.c 4.29 KB
edit raw normal view history
8ab8ba38d   Matthew Wilcox   ida: Start new te... 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
  // SPDX-License-Identifier: GPL-2.0+
  /*
   * test_ida.c: Test the IDA API
   * Copyright (c) 2016-2018 Microsoft Corporation
   * Copyright (c) 2018 Oracle Corporation
   * Author: Matthew Wilcox <willy@infradead.org>
   */
  
  #include <linux/idr.h>
  #include <linux/module.h>
  
  static unsigned int tests_run;
  static unsigned int tests_passed;
  
  #ifdef __KERNEL__
  void ida_dump(struct ida *ida) { }
  #endif
  #define IDA_BUG_ON(ida, x) do {						\
  	tests_run++;							\
  	if (x) {							\
  		ida_dump(ida);						\
  		dump_stack();						\
  	} else {							\
  		tests_passed++;						\
  	}								\
  } while (0)
0a3856392   Matthew Wilcox   test_ida: Move id... 
27
 
  /*
f272668de   Matthew Wilcox   test_ida: check_i... 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
   * Straightforward checks that allocating and freeing IDs work.
   */
  static void ida_check_alloc(struct ida *ida)
  {
  	int i, id;
  
  	for (i = 0; i < 10000; i++)
  		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  
  	ida_free(ida, 20);
  	ida_free(ida, 21);
  	for (i = 0; i < 3; i++) {
  		id = ida_alloc(ida, GFP_KERNEL);
  		IDA_BUG_ON(ida, id < 0);
  		if (i == 2)
  			IDA_BUG_ON(ida, id != 10000);
  	}
  
  	for (i = 0; i < 5000; i++)
  		ida_free(ida, i);
  
  	IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
  	ida_destroy(ida);
  
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  }
  
  /* Destroy an IDA with a single entry at @base */
  static void ida_check_destroy_1(struct ida *ida, unsigned int base)
  {
  	IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
  	IDA_BUG_ON(ida, ida_is_empty(ida));
  	ida_destroy(ida);
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  }
  
  /* Check that ida_destroy and ida_is_empty work */
  static void ida_check_destroy(struct ida *ida)
  {
  	/* Destroy an already-empty IDA */
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  	ida_destroy(ida);
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  
  	ida_check_destroy_1(ida, 0);
  	ida_check_destroy_1(ida, 1);
  	ida_check_destroy_1(ida, 1023);
  	ida_check_destroy_1(ida, 1024);
  	ida_check_destroy_1(ida, 12345678);
  }
  
  /*
0a3856392   Matthew Wilcox   test_ida: Move id... 
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
   * Check what happens when we fill a leaf and then delete it.  This may
   * discover mishandling of IDR_FREE.
   */
  static void ida_check_leaf(struct ida *ida, unsigned int base)
  {
  	unsigned long i;
  
  	for (i = 0; i < IDA_BITMAP_BITS; i++) {
  		IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  				base + i);
  	}
  
  	ida_destroy(ida);
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  
  	IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
  	IDA_BUG_ON(ida, ida_is_empty(ida));
  	ida_free(ida, 0);
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  }
161b47e31   Matthew Wilcox   test_ida: Move id... 
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
  /*
   * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
   * Allocating up to 2^31-1 should succeed, and then allocating the next one
   * should fail.
   */
  static void ida_check_max(struct ida *ida)
  {
  	unsigned long i, j;
  
  	for (j = 1; j < 65537; j *= 2) {
  		unsigned long base = (1UL << 31) - j;
  		for (i = 0; i < j; i++) {
  			IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  					base + i);
  		}
  		IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  				-ENOSPC);
  		ida_destroy(ida);
  		IDA_BUG_ON(ida, !ida_is_empty(ida));
  	}
  }
5c78b0b1e   Matthew Wilcox   test_ida: Convert... 
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
  /*
   * Check handling of conversions between exceptional entries and full bitmaps.
   */
  static void ida_check_conv(struct ida *ida)
  {
  	unsigned long i;
  
  	for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
  		IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
  		IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
  					GFP_KERNEL) != i + BITS_PER_LONG);
  		ida_free(ida, i + 1);
  		ida_free(ida, i + BITS_PER_LONG);
  		IDA_BUG_ON(ida, !ida_is_empty(ida));
  	}
  
  	for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
  		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  	for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
  		ida_free(ida, i - 1);
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  
  	for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
  		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  	for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
  		ida_free(ida, i - 1);
  	IDA_BUG_ON(ida, !ida_is_empty(ida));
  }
c994b1294   Matthew Wilcox   test_ida: Fix loc... 
149
 
  static DEFINE_IDA(ida);
8ab8ba38d   Matthew Wilcox   ida: Start new te... 
150
151
 
  static int ida_checks(void)
  {
8ab8ba38d   Matthew Wilcox   ida: Start new te... 
152
 
  	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
f272668de   Matthew Wilcox   test_ida: check_i... 
153
154
 
  	ida_check_alloc(&ida);
  	ida_check_destroy(&ida);
0a3856392   Matthew Wilcox   test_ida: Move id... 
155
156
157
 
  	ida_check_leaf(&ida, 0);
  	ida_check_leaf(&ida, 1024);
  	ida_check_leaf(&ida, 1024 * 64);
161b47e31   Matthew Wilcox   test_ida: Move id... 
158
 
  	ida_check_max(&ida);
5c78b0b1e   Matthew Wilcox   test_ida: Convert... 
159
 
  	ida_check_conv(&ida);
8ab8ba38d   Matthew Wilcox   ida: Start new te... 
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
  
  	printk("IDA: %u of %u tests passed
  ", tests_passed, tests_run);
  	return (tests_run != tests_passed) ? 0 : -EINVAL;
  }
  
  static void ida_exit(void)
  {
  }
  
  module_init(ida_checks);
  module_exit(ida_exit);
  MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
  MODULE_LICENSE("GPL");