]> mj.ucw.cz Git - libucw.git/blob - lib/db-test.c
install sorter-globals.h header
[libucw.git] / lib / db-test.c
1 /*
2  *      UCW Library -- Database Manager -- Tests and Benchmarks
3  *
4  *      (c) 1999 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 #if 1
11 #include "lib/db.c"
12 #define NAME "SDBM"
13 #else
14 #include "lib/db-emul.c"
15 #define NAME "GDBM"
16 #endif
17
18 #include <stdlib.h>
19 #include <unistd.h>
20 #include <stdarg.h>
21 #include <sys/stat.h>
22
23 static struct sdbm_options opts = {
24   flags: SDBM_CREAT | SDBM_WRITE,
25   name: "db.test",
26   page_order: 10,
27   cache_size: 1024,
28   key_size: -1,
29   val_size: -1
30 };
31
32 static struct sdbm *d;
33 static int key_min, key_max;            /* min<0 -> URL distribution */
34 static int val_min, val_max;
35 static int num_keys;                    /* Number of distinct keys */
36 static int verbose;
37
38 static void
39 help(void)
40 {
41   printf("Usage: dbtest [<options>] <commands>\n\
42 \n\
43 Options:\n\
44 -c<n>           Use cache of <n> pages\n\
45 -p<n>           Use pages of order <n>\n\
46 -k<n>           Use key size <n>\n\
47 -k<m>-<n>       Use key size uniformly distributed between <m> and <n>\n\
48 -kU             Use keys with URL distribution\n\
49 -n<n>           Number of distinct keys\n\
50 -d<m>[-<n>]     Use specified value size (see -k<m>-<n>)\n\
51 -t              Perform the tests on an existing database file\n\
52 -v              Be verbose\n\
53 -s              Turn on synchronous mode\n\
54 -S              Turn on supersynchronous mode\n\
55 -F              Turn on fast mode\n\
56 \n\
57 Commands:\n\
58 c               Fill database\n\
59 r               Rewrite database\n\
60 f[<p>%%][<n>]   Find <n> records with probability of success <p>%% (default=100)\n\
61 F[<p>%%][<n>]   Find, but don't fetch values\n\
62 d               Delete records\n\
63 w               Walk database\n\
64 W               Walk, but don't fetch values\n\
65 ");
66   exit(0);
67 }
68
69 static uns
70 krand(uns kn)
71 {
72   return kn * 2000000011;
73 }
74
75 static uns
76 gen_url_size(uns rnd)
77 {
78   uns l, m, r;
79   static uns utable[] = {
80 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 22, 108, 245, 481, 979, 3992, 7648, 13110, 19946, 27256, 34993, 43222, 52859, 64563,
81 80626, 117521, 147685, 188364, 233174, 290177, 347132, 407231, 465787, 540931, 628601, 710246, 808671, 922737, 1025691, 1138303,
82 1238802, 1344390, 1443843, 1533207, 1636494, 1739082, 1826911, 1910725, 1993940, 2094365, 2188987, 2267827, 2350190, 2441980,
83 2520713, 2593654, 2668632, 2736009, 2808356, 2889682, 2959300, 3017945, 3086488, 3146032, 3204818, 3251897, 3307001, 3349388,
84 3392798, 3433429, 3476765, 3529107, 3556884, 3585120, 3633005, 3677697, 3699561, 3716660, 3739823, 3765154, 3795096, 3821184,
85 3858117, 3908757, 3929095, 3943264, 3957033, 3969588, 3983441, 3994630, 4005413, 4028890, 4039678, 4058007, 4071906, 4087029,
86 4094233, 4105259, 4111603, 4120338, 4127364, 4133983, 4140310, 4144843, 4150565, 4155974, 4165132, 4170648, 4176811, 4187118,
87 4190866, 4199051, 4206686, 4216122, 4226109, 4233721, 4254123, 4261792, 4270396, 4276650, 4282932, 4291738, 4295932, 4299370,
88 4304011, 4307098, 4311866, 4318168, 4325730, 4329774, 4332946, 4336305, 4339770, 4345237, 4349038, 4356129, 4362872, 4366542,
89 4371077, 4374524, 4376733, 4378794, 4380652, 4382340, 4383552, 4385952, 4386914, 4393123, 4394106, 4395142, 4396593, 4399112,
90 4399909, 4401015, 4401780, 4402616, 4403454, 4404481, 4405231, 4405947, 4406886, 4408364, 4409159, 4409982, 4410872, 4412010,
91 4413341, 4414161, 4415673, 4417135, 4418032, 4419117, 4419952, 4420677, 4421387, 4421940, 4422469, 4423210, 4423696, 4424274,
92 4424982, 4425665, 4426363, 4427018, 4427969, 4428992, 4429791, 4430804, 4432601, 4433440, 4434157, 4434967, 4436280, 4439784,
93 4444255, 4445544, 4446416, 4447620, 4449638, 4453004, 4455470, 4456982, 4457956, 4458617, 4459538, 4460007, 4460377, 4460768,
94 4461291, 4461520, 4461678, 4461911, 4462063, 4462239, 4462405, 4462607, 4462666, 4462801, 4462919, 4463108, 4463230, 4463438,
95 4463530, 4463698, 4463779, 4463908, 4463991, 4464138, 4464188, 4464391, 4464580, 4464868, 4464980, 4465174, 4465255, 4465473,
96 4465529, 4465681, 4465746, 4465916, 4465983, 4466171, 4466248, 4466430, 4466560, 4466751, 4466930, 4467807, 4468847, 4469940,
97 4470344, 4470662, 4470716, 4471120, 4471389, 4471814, 4472141, 4472545, 4472687, 4473051, 4473253, 4473603, 4473757, 4474065,
98 4474125, 4474354, 4474428, 4474655, 4474705, 4474841, 4474858, 4475133, 4475201, 4475327, 4475367, 4475482, 4475533, 4475576,
99 4475586, 4475616, 4475637, 4475659, 4475696, 4475736, 4475775, 4475794, 4476156, 4476711, 4477004, 4477133, 4477189, 4477676,
100 4477831, 4477900, 4477973, 4477994, 4478011, 4478040, 4478063, 4478085, 4478468, 4478715, 4479515, 4480034, 4481804, 4483259,
101 4483866, 4484202, 4484932, 4485693, 4486184, 4486549, 4486869, 4487405, 4487639, 4487845, 4488086, 4488256, 4488505, 4488714,
102 4492669, 4496233, 4497738, 4498122, 4498653, 4499862, 4501169, 4501627, 4501673, 4501811, 4502182, 4502475, 4502533, 4502542,
103 4502548, 4502733, 4503389, 4504381, 4505070, 4505378, 4505814, 4506031, 4506336, 4506642, 4506845, 4506971, 4506986, 4507016,
104 4507051, 4507098, 4507107, 4507114, 4507139, 4507478, 4507643, 4507674, 4507694, 4507814, 4507894, 4507904, 4507929, 4507989,
105 4508023, 4508047, 4508053, 4508063, 4508075, 4508092, 4508104, 4508113, 4508239, 4508285, 4508324, 4508335, 4508340, 4508378,
106 4508405, 4508419, 4508436, 4508449, 4508470, 4508488, 4508515, 4508541, 4508564, 4508570, 4508584, 4508594, 4508607, 4508634,
107 4508652, 4508665, 4508673, 4508692, 4508704, 4508742, 4508755, 4508773, 4508788, 4508798, 4508832, 4508869, 4508885, 4508905,
108 4508915, 4508947, 4508956, 4509061, 4509070, 4509357, 4509368, 4509380, 4509393, 4509401, 4509412, 4509426, 4509438, 4509451,
109 4509461, 4509473, 4509489, 4509498, 4509512, 4509537, 4509568, 4509582, 4509621, 4509629, 4509747, 4509766, 4509776, 4509795,
110 4509802, 4509813, 4509822, 4509829, 4509834, 4509844, 4509854, 4509863, 4509868, 4509875, 4509886, 4509898, 4509908, 4509920,
111 4509932, 4509941, 4509949, 4509955, 4509967, 4509972, 4509979, 4509987, 4509999, 4510002, 4510010, 4510014, 4510018, 4510025,
112 4510028, 4510049, 4510055, 4510061, 4510068, 4510079, 4510085, 4510091, 4510098, 4510102, 4510104, 4510110, 4510121, 4510128,
113 4510132, 4510138, 4510144, 4510145, 4510153, 4510161, 4510174, 4510196, 4510199, 4510208, 4510209, 4510212, 4510216, 4510217,
114 4510219, 4510222, 4510228, 4510231, 4510236, 4510241, 4510245, 4510248, 4510250, 4510254, 4510255, 4510261, 4510262, 4510266,
115 4510266, 4510271, 4510285, 4510287, 4510291, 4510295, 4510303, 4510306, 4510308, 4510310, 4510314, 4510319, 4510320, 4510324,
116 4510328, 4510333, 4510333, 4510336, 4510340, 4510342, 4510348, 4510353, 4510359, 4510362, 4510365, 4510371, 4510373, 4510375,
117 4510378, 4510380, 4510385, 4510389, 4510391, 4510391, 4510394, 4510396, 4510397, 4510398, 4510400, 4510403, 4510406, 4510407,
118 4510408, 4510409, 4510411, 4510413, 4510417, 4510417, 4510419, 4510422, 4510426, 4510427, 4510430, 4510435, 4510437, 4510439,
119 4510440, 4510442, 4510442, 4510446, 4510447, 4510448, 4510450, 4510451, 4510451, 4510453, 4510454, 4510455, 4510457, 4510460,
120 4510460, 4510460, 4510462, 4510463, 4510466, 4510468, 4510472, 4510475, 4510480, 4510482, 4510483, 4510486, 4510488, 4510492,
121 4510494, 4510497, 4510497, 4510499, 4510503, 4510505, 4510506, 4510507, 4510509, 4510512, 4510514, 4510527, 4510551, 4510553,
122 4510554, 4510555, 4510556, 4510558, 4510561, 4510562, 4510566, 4510567, 4510568, 4510570, 4510573, 4510574, 4510586, 4510603,
123 4510605, 4510607, 4510610, 4510610, 4510613, 4510613, 4510614, 4510614, 4510615, 4510616, 4510616, 4510620, 4510622, 4510623,
124 4510624, 4510627, 4510628, 4510630, 4510631, 4510632, 4510634, 4510634, 4510634, 4510636, 4510636, 4510639, 4510639, 4510640,
125 4510643, 4510647, 4510649, 4510650, 4510653, 4510653, 4510653, 4510653, 4510656, 4510659, 4510661, 4510664, 4510665, 4510669,
126 4510672, 4510673, 4510674, 4510675, 4510680, 4510683, 4510684, 4510686, 4510687, 4510690, 4510691, 4510693, 4510693, 4510697,
127 4510699, 4510700, 4510703, 4510704, 4510709, 4510711, 4510713, 4510713, 4510720, 4510720, 4510722, 4510724, 4510727, 4510729,
128 4510735, 4510735, 4510738, 4510740, 4510744, 4510745, 4510746, 4510748, 4510754, 4510756, 4510758, 4510761, 4510764, 4510766,
129 4510768, 4510768, 4510770, 4510770, 4510772, 4510774, 4510775, 4510775, 4510775, 4510776, 4510777, 4510780, 4510782, 4510783,
130 4510785, 4510786, 4510788, 4510789, 4510791, 4510793, 4510793, 4510793, 4510795, 4510795, 4510799, 4510803, 4510804, 4510804,
131 4510804, 4510805, 4510807, 4510809, 4510811, 4510811, 4510813, 4510815, 4510815, 4510816, 4510819, 4510820, 4510824, 4510827,
132 4510829, 4510829, 4510830, 4510833, 4510835, 4510837, 4510838, 4510838, 4510839, 4510840, 4510840, 4510842, 4510842, 4510843,
133 4510845, 4510845, 4510845, 4510847, 4510848, 4510848, 4510848, 4510850, 4510853, 4510855, 4510857, 4510859, 4510861, 4510862,
134 4510864, 4510865, 4510865, 4510865, 4510869, 4510869, 4510869, 4510869, 4510869, 4510870, 4510870, 4510872, 4510872, 4510873,
135 4510874, 4510875, 4510875, 4510877, 4510879, 4510879, 4510879, 4510879, 4510880, 4510881, 4510882, 4510883, 4510884, 4510885,
136 4510886, 4510887, 4510890, 4510890, 4510891, 4510892, 4510892, 4510893, 4510893, 4510895, 4510895, 4510896, 4510897, 4510899,
137 4510901, 4510901, 4510901, 4510902, 4510903, 4510903, 4510903, 4510905, 4510905, 4510906, 4510906, 4510907, 4510907, 4510909,
138 4510910, 4510911, 4510911, 4510911, 4510913, 4510913, 4510914, 4510914, 4510914, 4510915, 4510916, 4510918, 4510918, 4510919,
139 4510919, 4510919, 4510920, 4510921, 4510922, 4510923, 4510924, 4510924, 4510924, 4510924, 4510926, 4510927, 4510928, 4510928,
140 4510928, 4510928, 4510928, 4510930, 4510933, 4510935, 4510935, 4510935, 4510935, 4510935, 4510936, 4510938, 4510947, 4510966,
141 4510967, 4510969, 4510973, 4510973, 4510974, 4510974, 4510974, 4510974, 4510974, 4510974, 4510975, 4510976, 4510976, 4510976,
142 4510976, 4510976, 4510976, 4510976, 4510977, 4510979, 4510979, 4510979, 4510979, 4510979, 4510979, 4510980, 4510980, 4510980,
143 4510980, 4510981, 4510981, 4510981, 4510982, 4510982, 4510982, 4510982, 4510982, 4510982, 4510982, 4510983, 4510983, 4510984,
144 4510984, 4510984, 4510984, 4510984, 4510985, 4510985, 4510985, 4510985, 4510987, 4510987, 4510987, 4510988, 4510988, 4510989,
145 4510989, 4510989, 4510989, 4510989, 4510990, 4510990, 4510990, 4510990, 4510990, 4510990, 4510990, 4510991, 4510991, 4510991,
146 4510991, 4510991, 4510991, 4510991, 4510992, 4510992, 4510992, 4510992, 4510992, 4510992, 4510992, 4510993, 4510993, 4510993,
147 4510994, 4510994, 4510994, 4510994, 4510995, 4510995, 4510996, 4510997, 4510998, 4510999, 4510999, 4511000, 4511000, 4511001,
148 4511001, 4511002, 4511002, 4511002, 4511003, 4511004, 4511004, 4511004, 4511004, 4511005, 4511006, 4511008, 4511008, 4511008,
149 4511009, 4511009, 4511009, 4511009, 4511010, 4511011, 4511011, 4511012, 4511012, 4511012, 4511012, 4511013, 4511013, 4511014,
150 4511014, 4511014, 4511014, 4511015, 4511018, 4511018, 4511018, 4511018, 4511018, 4511018, 4511018, 4511020, 4511020, 4511020,
151 4511020, 4511020, 4511020, 4511020, 4511021, 4511021, 4511021, 4511021, 4511021, 4511021, 4511021, 4511021, 4511021, 4511021,
152 4511021
153   };
154
155   rnd %= utable[1024];
156   l = 0; r = 1023;
157   while (l < r)
158     {
159       m = (l+r)/2;
160       if (utable[m] == rnd)
161         return m;
162       if (utable[m] >= rnd)
163         r = m - 1;
164       else
165         l = m + 1;
166     }
167   return l;
168 }
169
170 static uns
171 gen_size(uns min, uns max, uns rnd)
172 {
173   if (min == max)
174     return min;
175   else
176     return min + rnd % (max - min + 1);
177 }
178
179 static void
180 gen_random(byte *buf, uns size, uns kn)
181 {
182   kn = (kn + 0x36221057) ^ (kn << 24) ^ (kn << 15);
183   while (size--)
184     {
185       *buf++ = kn >> 24;
186       kn = kn*257 + 17;
187     }
188 }
189
190 static int
191 keygen(byte *buf, uns kn)
192 {
193   uns size, rnd;
194
195   rnd = krand(kn);
196   if (key_min < 0)
197     size = gen_url_size(rnd);
198   else
199     size = gen_size(key_min, key_max, rnd);
200   *buf++ = kn >> 24;
201   *buf++ = kn >> 16;
202   *buf++ = kn >> 8;
203   *buf++ = kn;
204   if (size < 4)
205     return 4;
206   gen_random(buf, size-4, kn);
207   return size;
208 }
209
210 static int
211 valgen(byte *buf, uns kn)
212 {
213   uns size = gen_size(val_min, val_max, krand(kn));
214   gen_random(buf, size, kn);
215   return size;
216 }
217
218 static uns
219 keydec(byte *buf)
220 {
221   return (buf[0] << 24) | (buf[1] << 16) | (buf[2] << 8) | buf[3];
222 }
223
224 static void
225 verb(char *msg, ...)
226 {
227   int cat = 1;
228   va_list args;
229
230   va_start(args, msg);
231   if (msg[0] == '^' && msg[1])
232     {
233       cat = msg[1] - '0';
234       msg += 2;
235     }
236   if (verbose >= cat)
237     vfprintf(stderr, msg, args);
238   va_end(args);
239 }
240
241 static void
242 parse_size(int *min, int *max, char *c)
243 {
244   char *d;
245
246   if ((d = strchr(c, '-')))
247     {
248       *d++ = 0;
249       *min = atol(c);
250       *max = atol(d);
251     }
252   else
253     *min = *max = atol(c);
254 }
255
256 #define PROGRESS(i) if ((verbose > 2) || (verbose > 1 && !(i & 1023))) fprintf(stderr, "%d\r", i)
257
258 int main(int argc, char **argv)
259 {
260   int c, i, j, k, l, m;
261   byte kb[2048], vb[2048], vb2[2048];
262   uns ks, vs, vs2, perc, cnt;
263   char *ch;
264   int dont_delete = 0;
265
266   log_init("dbtest");
267   setvbuf(stdout, NULL, _IONBF, 0);
268   setvbuf(stderr, NULL, _IONBF, 0);
269   while ((c = getopt(argc, argv, "c:p:k:n:d:vsStF")) >= 0)
270     switch (c)
271       {
272       case 'c':
273         opts.cache_size = atol(optarg);
274         break;
275       case 'p':
276         opts.page_order = atol(optarg);
277         break;
278       case 'k':
279         if (!strcmp(optarg, "U"))
280           key_min = key_max = -1;
281         else
282           parse_size(&key_min, &key_max, optarg);
283         break;
284       case 'n':
285         num_keys = atol(optarg);
286         break;
287       case 'd':
288         parse_size(&val_min, &val_max, optarg);
289         break;
290       case 'v':
291         verbose++;
292         break;
293       case 's':
294         opts.flags |= SDBM_SYNC;
295         break;
296       case 'S':
297         opts.flags |= SDBM_SYNC | SDBM_FSYNC;
298         break;
299       case 'F':
300         opts.flags |= SDBM_FAST;
301         break;
302       case 't':
303         dont_delete = 1;
304         break;
305       default:
306         help();
307       }
308
309   if (key_min >= 0 && key_min < 4)
310     key_min = key_max = 4;
311   if (key_min == key_max && key_min >= 0)
312     opts.key_size = key_min;
313   if (val_min == val_max)
314     opts.val_size = val_min;
315   if (!num_keys)
316     die("Number of keys not given");
317
318   printf(NAME " benchmark: %d records, keys ", num_keys);
319   if (key_min < 0)
320     printf("<URL>");
321   else
322     printf("%d-%d", key_min, key_max);
323   printf(", values %d-%d, page size %d, cache %d pages\n", val_min, val_max, 1 << opts.page_order, opts.cache_size);
324
325   verb("OPEN(%s, key=%d, val=%d, cache=%d, pgorder=%d)\n", opts.name, opts.key_size, opts.val_size,
326        opts.cache_size, opts.page_order);
327   if (!dont_delete)
328     unlink(opts.name);
329   d = sdbm_open(&opts);
330   if (!d)
331     die("open failed: %m");
332
333   while (optind < argc)
334     {
335       char *o = argv[optind++];
336       init_timer();
337       switch (*o)
338         {
339         case 'c':
340           printf("create %d: ", num_keys);
341           for(i=0; i<num_keys; i++)
342             {
343               PROGRESS(i);
344               ks = keygen(kb, i);
345               vs = valgen(vb, i);
346               if (sdbm_store(d, kb, ks, vb, vs) != 1) die("store failed");
347             }
348           break;
349         case 'r':
350           printf("rewrite %d: ", num_keys);
351           for(i=0; i<num_keys; i++)
352             {
353               PROGRESS(i);
354               ks = keygen(kb, i);
355               vs = valgen(vb, i);
356               if (sdbm_replace(d, kb, ks, vb, vs) != 1) die("replace failed");
357             }
358           break;
359         case 'f':
360         case 'F':
361           c = (*o++ == 'f');
362           if ((ch = strchr(o, '%')))
363             {
364               *ch++ = 0;
365               perc = atol(o);
366             }
367           else
368             {
369               ch = o;
370               perc = 100;
371             }
372           cnt = atol(ch);
373           if (!cnt)
374             {
375               cnt = num_keys;
376               m = (perc == 100);
377             }
378           else
379             m = 0;
380           printf("%s fetch %d (%d%% success, with%s values): ", (m ? "sequential" : "random"), cnt, perc, (c ? "" : "out"));
381           i = -1;
382           while (cnt--)
383             {
384               if (m)
385                 i++;
386               else
387                 i = random_max(num_keys) + ((random_max(100) < perc) ? 0 : num_keys);
388               PROGRESS(i);
389               ks = keygen(kb, i);
390               if (c)
391                 {
392                   vs2 = sizeof(vb2);
393                   j = sdbm_fetch(d, kb, ks, vb2, &vs2);
394                 }
395               else
396                 j = sdbm_fetch(d, kb, ks, NULL, NULL);
397               if (j < 0)
398                 die("fetch: error %d", j);
399               if ((i < num_keys) != j)
400                 die("fetch mismatch at key %d, res %d", i, j);
401               if (c && j)
402                 {
403                   vs = valgen(vb, i);
404                   if (vs != vs2 || memcmp(vb, vb2, vs))
405                     die("fetch data mismatch at key %d: %d,%d", i, vs, vs2);
406                 }
407             }
408           break;
409         case 'd':
410           printf("delete %d: ", num_keys);
411           for(i=0; i<num_keys; i++)
412             {
413               PROGRESS(i);
414               ks = keygen(kb, i);
415               if (sdbm_delete(d, kb, ks) != 1) die("delete failed");
416             }
417           break;
418         case 'w':
419         case 'W':
420           c = (*o == 'w');
421           i = k = l = m = 0;
422           printf("walk %d (with%s keys): ", num_keys, (c ? "" : "out"));
423           sdbm_rewind(d);
424           for(;;)
425             {
426               ks = sizeof(kb);
427               vs = sizeof(vb);
428               if (c)
429                 j = sdbm_get_next(d, kb, &ks, vb, &vs);
430               else
431                 j = sdbm_get_next(d, kb, &ks, NULL, NULL);
432               if (!j)
433                 break;
434               if (ks < 4)
435                 die("get_next: too short");
436               i = keydec(kb);
437               if (i < 0 || i >= num_keys)
438                 die("get_next: %d out of range", i);
439               PROGRESS(i);
440               vs2 = keygen(vb2, i);
441               if (ks != vs2 || memcmp(kb, vb2, ks))
442                 die("get_next: key mismatch at %d", i);
443               if (c)
444                 {
445                   vs2 = valgen(vb2, i);
446                   if (vs != vs2 || memcmp(vb, vb2, vs))
447                     die("get_next: data mismatch at %d", i);
448                 }
449               l += k;
450               m += i;
451               k++;
452             }
453           if (k != num_keys)
454             die("fetch: wrong # of keys: %d != %d", k, num_keys);
455           if (l != m)
456             die("fetch: wrong checksum: %d != %d", l, m);
457           break;
458         default:
459           help();
460         }
461       sdbm_sync(d);
462       printf("%d ms\n", get_timer());
463     }
464
465   verb("CLOSE\n");
466   sdbm_close(d);
467
468   {
469     struct stat st;
470     if (stat(opts.name, &st)) die("stat: %m");
471     printf("file size: %d bytes\n", (int) st.st_size);
472   }
473   return 0;
474 }