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