tdb2: use immobile free buckets, rename tests to show some ordering.
[ccan] / ccan / tdb2 / io.c
1  /* 
2    Unix SMB/CIFS implementation.
3
4    trivial database library
5
6    Copyright (C) Andrew Tridgell              1999-2005
7    Copyright (C) Paul `Rusty' Russell              2000
8    Copyright (C) Jeremy Allison                    2000-2003
9    Copyright (C) Rusty Russell                     2010
10
11      ** NOTE! The following LGPL license applies to the tdb
12      ** library. This does NOT imply that all of Samba is released
13      ** under the LGPL
14
15    This library is free software; you can redistribute it and/or
16    modify it under the terms of the GNU Lesser General Public
17    License as published by the Free Software Foundation; either
18    version 3 of the License, or (at your option) any later version.
19
20    This library is distributed in the hope that it will be useful,
21    but WITHOUT ANY WARRANTY; without even the implied warranty of
22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23    Lesser General Public License for more details.
24
25    You should have received a copy of the GNU Lesser General Public
26    License along with this library; if not, see <http://www.gnu.org/licenses/>.
27 */
28 #include "private.h"
29 #include <ccan/likely/likely.h>
30
31 void tdb_munmap(struct tdb_context *tdb)
32 {
33         if (tdb->flags & TDB_INTERNAL)
34                 return;
35
36         if (tdb->map_ptr) {
37                 munmap(tdb->map_ptr, tdb->map_size);
38                 tdb->map_ptr = NULL;
39         }
40 }
41
42 void tdb_mmap(struct tdb_context *tdb)
43 {
44         if (tdb->flags & TDB_INTERNAL)
45                 return;
46
47         if (tdb->flags & TDB_NOMMAP)
48                 return;
49
50         tdb->map_ptr = mmap(NULL, tdb->map_size, 
51                             PROT_READ|(tdb->read_only? 0:PROT_WRITE), 
52                             MAP_SHARED, tdb->fd, 0);
53
54         /*
55          * NB. When mmap fails it returns MAP_FAILED *NOT* NULL !!!!
56          */
57         if (tdb->map_ptr == MAP_FAILED) {
58                 tdb->map_ptr = NULL;
59                 tdb->log(tdb, TDB_DEBUG_WARNING, tdb->log_priv,
60                          "tdb_mmap failed for size %lld (%s)\n", 
61                          (long long)tdb->map_size, strerror(errno));
62         }
63 }
64
65 /* check for an out of bounds access - if it is out of bounds then
66    see if the database has been expanded by someone else and expand
67    if necessary 
68    note that "len" is the minimum length needed for the db
69 */
70 static int tdb_oob(struct tdb_context *tdb, tdb_off_t len, bool probe)
71 {
72         struct stat st;
73         int ret;
74
75         if (len <= tdb->map_size)
76                 return 0;
77         if (tdb->flags & TDB_INTERNAL) {
78                 if (!probe) {
79                         /* Ensure ecode is set for log fn. */
80                         tdb->ecode = TDB_ERR_IO;
81                         tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
82                                  "tdb_oob len %lld beyond internal"
83                                  " malloc size %lld\n",
84                                  (long long)len,
85                                  (long long)tdb->map_size);
86                 }
87                 return -1;
88         }
89
90         if (tdb_lock_expand(tdb, F_RDLCK) != 0)
91                 return -1;
92
93         ret = fstat(tdb->fd, &st);
94
95         tdb_unlock_expand(tdb, F_RDLCK);
96
97         if (ret == -1) {
98                 tdb->ecode = TDB_ERR_IO;
99                 return -1;
100         }
101
102         if (st.st_size < (size_t)len) {
103                 if (!probe) {
104                         /* Ensure ecode is set for log fn. */
105                         tdb->ecode = TDB_ERR_IO;
106                         tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
107                                  "tdb_oob len %lld beyond eof at %lld\n",
108                                  (long long)len, (long long)st.st_size);
109                 }
110                 return -1;
111         }
112
113         /* Unmap, update size, remap */
114         tdb_munmap(tdb);
115
116         tdb->map_size = st.st_size;
117         tdb_mmap(tdb);
118         return 0;
119 }
120
121 static void *tdb_direct(struct tdb_context *tdb, tdb_off_t off, size_t len)
122 {
123         if (unlikely(!tdb->map_ptr))
124                 return NULL;
125
126         /* FIXME: We can do a subset of this! */
127         if (tdb->transaction)
128                 return NULL;
129
130         if (unlikely(tdb_oob(tdb, off + len, true) == -1))
131                 return NULL;
132         return (char *)tdb->map_ptr + off;
133 }
134
135 /* Either make a copy into pad and return that, or return ptr into mmap. */
136 /* Note: pad has to be a real object, so we can't get here if len
137  * overflows size_t */
138 void *tdb_get(struct tdb_context *tdb, tdb_off_t off, void *pad, size_t len)
139 {
140         if (likely(!(tdb->flags & TDB_CONVERT))) {
141                 void *ret = tdb_direct(tdb, off, len);
142                 if (ret)
143                         return ret;
144         }
145         return tdb_read_convert(tdb, off, pad, len) == -1 ? NULL : pad;
146 }
147
148 /* Endian conversion: we only ever deal with 8 byte quantities */
149 void *tdb_convert(const struct tdb_context *tdb, void *buf, tdb_len_t size)
150 {
151         if (unlikely((tdb->flags & TDB_CONVERT)) && buf) {
152                 uint64_t i, *p = (uint64_t *)buf;
153                 for (i = 0; i < size / 8; i++)
154                         p[i] = bswap_64(p[i]);
155         }
156         return buf;
157 }
158
159 /* Return first non-zero offset in num offset array, or num. */
160 /* FIXME: Return the off? */
161 uint64_t tdb_find_nonzero_off(struct tdb_context *tdb, tdb_off_t off,
162                               uint64_t num)
163 {
164         uint64_t i;
165         const uint64_t *val;
166
167         /* Zero vs non-zero is the same unconverted: minor optimization. */
168         val = tdb_access_read(tdb, off, num * sizeof(tdb_off_t), false);
169         if (!val)
170                 return num;
171
172         for (i = 0; i < num; i++) {
173                 if (val[i])
174                         break;
175         }
176         tdb_access_release(tdb, val);
177         return i;
178 }
179
180 /* Return first zero offset in num offset array, or num. */
181 uint64_t tdb_find_zero_off(struct tdb_context *tdb, tdb_off_t off,
182                            uint64_t num)
183 {
184         uint64_t i;
185         const uint64_t *val;
186
187         /* Zero vs non-zero is the same unconverted: minor optimization. */
188         val = tdb_access_read(tdb, off, num * sizeof(tdb_off_t), false);
189         if (!val)
190                 return num;
191
192         for (i = 0; i < num; i++) {
193                 if (!val[i])
194                         break;
195         }
196         tdb_access_release(tdb, val);
197         return i;
198 }
199
200 int zero_out(struct tdb_context *tdb, tdb_off_t off, tdb_len_t len)
201 {
202         char buf[8192] = { 0 };
203         void *p = tdb_direct(tdb, off, len);
204         if (p) {
205                 memset(p, 0, len);
206                 return 0;
207         }
208         while (len) {
209                 unsigned todo = len < sizeof(buf) ? len : sizeof(buf);
210                 if (tdb->methods->write(tdb, off, buf, todo) == -1)
211                         return -1;
212                 len -= todo;
213                 off += todo;
214         }
215         return 0;
216 }
217
218 tdb_off_t tdb_read_off(struct tdb_context *tdb, tdb_off_t off)
219 {
220         tdb_off_t pad, *ret;
221
222         ret = tdb_get(tdb, off, &pad, sizeof(pad));
223         if (!ret) {
224                 return TDB_OFF_ERR;
225         }
226         return *ret;
227 }
228
229 /* Even on files, we can get partial writes due to signals. */
230 bool tdb_pwrite_all(int fd, const void *buf, size_t len, tdb_off_t off)
231 {
232         while (len) {
233                 ssize_t ret;
234                 ret = pwrite(fd, buf, len, off);
235                 if (ret < 0)
236                         return false;
237                 if (ret == 0) {
238                         errno = ENOSPC;
239                         return false;
240                 }
241                 buf = (char *)buf + ret;
242                 off += ret;
243                 len -= ret;
244         }
245         return true;
246 }
247
248 /* Even on files, we can get partial reads due to signals. */
249 bool tdb_pread_all(int fd, void *buf, size_t len, tdb_off_t off)
250 {
251         while (len) {
252                 ssize_t ret;
253                 ret = pread(fd, buf, len, off);
254                 if (ret < 0)
255                         return false;
256                 if (ret == 0) {
257                         /* ETOOSHORT? */
258                         errno = EWOULDBLOCK;
259                         return false;
260                 }
261                 buf = (char *)buf + ret;
262                 off += ret;
263                 len -= ret;
264         }
265         return true;
266 }
267
268 bool tdb_read_all(int fd, void *buf, size_t len)
269 {
270         while (len) {
271                 ssize_t ret;
272                 ret = read(fd, buf, len);
273                 if (ret < 0)
274                         return false;
275                 if (ret == 0) {
276                         /* ETOOSHORT? */
277                         errno = EWOULDBLOCK;
278                         return false;
279                 }
280                 buf = (char *)buf + ret;
281                 len -= ret;
282         }
283         return true;
284 }
285
286 /* write a lump of data at a specified offset */
287 static int tdb_write(struct tdb_context *tdb, tdb_off_t off, 
288                      const void *buf, tdb_len_t len)
289 {
290         if (len == 0) {
291                 return 0;
292         }
293
294         if (tdb->read_only) {
295                 tdb->ecode = TDB_ERR_RDONLY;
296                 return -1;
297         }
298
299         if (tdb->methods->oob(tdb, off + len, 0) != 0)
300                 return -1;
301
302         if (tdb->map_ptr) {
303                 memcpy(off + (char *)tdb->map_ptr, buf, len);
304         } else {
305                 if (!tdb_pwrite_all(tdb->fd, buf, len, off)) {
306                         tdb->ecode = TDB_ERR_IO;
307                         tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
308                                  "tdb_write failed at %llu len=%llu (%s)\n",
309                                  off, len, strerror(errno));
310                         return -1;
311                 }
312         }
313         return 0;
314 }
315
316 /* read a lump of data at a specified offset */
317 static int tdb_read(struct tdb_context *tdb, tdb_off_t off, void *buf,
318                     tdb_len_t len)
319 {
320         if (tdb->methods->oob(tdb, off + len, 0) != 0) {
321                 return -1;
322         }
323
324         if (tdb->map_ptr) {
325                 memcpy(buf, off + (char *)tdb->map_ptr, len);
326         } else {
327                 if (!tdb_pread_all(tdb->fd, buf, len, off)) {
328                         /* Ensure ecode is set for log fn. */
329                         tdb->ecode = TDB_ERR_IO;
330                         tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
331                                  "tdb_read failed at %lld "
332                                  "len=%lld (%s) map_size=%lld\n",
333                                  (long long)off, (long long)len,
334                                  strerror(errno),
335                                  (long long)tdb->map_size);
336                         return -1;
337                 }
338         }
339         return 0;
340 }
341
342 int tdb_write_convert(struct tdb_context *tdb, tdb_off_t off,
343                       const void *rec, size_t len)
344 {
345         int ret;
346         if (unlikely((tdb->flags & TDB_CONVERT))) {
347                 void *conv = malloc(len);
348                 if (!conv) {
349                         tdb->ecode = TDB_ERR_OOM;
350                         tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
351                                  "tdb_write: no memory converting %zu bytes\n",
352                                  len);
353                         return -1;
354                 }
355                 memcpy(conv, rec, len);
356                 ret = tdb->methods->write(tdb, off,
357                                           tdb_convert(tdb, conv, len), len);
358                 free(conv);
359         } else
360                 ret = tdb->methods->write(tdb, off, rec, len);
361
362         return ret;
363 }
364
365 int tdb_read_convert(struct tdb_context *tdb, tdb_off_t off,
366                       void *rec, size_t len)
367 {
368         int ret = tdb->methods->read(tdb, off, rec, len);
369         tdb_convert(tdb, rec, len);
370         return ret;
371 }
372
373 int tdb_write_off(struct tdb_context *tdb, tdb_off_t off, tdb_off_t val)
374 {
375         return tdb_write_convert(tdb, off, &val, sizeof(val));
376 }
377
378 /* read a lump of data, allocating the space for it */
379 void *tdb_alloc_read(struct tdb_context *tdb, tdb_off_t offset, tdb_len_t len)
380 {
381         void *buf;
382
383         /* some systems don't like zero length malloc */
384         buf = malloc(len ? len : 1);
385         if (unlikely(!buf)) {
386                 tdb->ecode = TDB_ERR_OOM;
387                 tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
388                          "tdb_alloc_read malloc failed len=%lld\n",
389                          (long long)len);
390         } else if (unlikely(tdb->methods->read(tdb, offset, buf, len))) {
391                 free(buf);
392                 buf = NULL;
393         }
394         return buf;
395 }
396
397 uint64_t hash_record(struct tdb_context *tdb, tdb_off_t off)
398 {
399         struct tdb_used_record pad, *r;
400         const void *key;
401         uint64_t klen, hash;
402
403         r = tdb_get(tdb, off, &pad, sizeof(pad));
404         if (!r)
405                 /* FIXME */
406                 return 0;
407
408         klen = rec_key_length(r);
409         key = tdb_access_read(tdb, off + sizeof(pad), klen, false);
410         if (!key)
411                 return 0;
412
413         hash = tdb_hash(tdb, key, klen);
414         tdb_access_release(tdb, key);
415         return hash;
416 }
417
418 static int fill(struct tdb_context *tdb,
419                 const void *buf, size_t size,
420                 tdb_off_t off, tdb_len_t len)
421 {
422         while (len) {
423                 size_t n = len > size ? size : len;
424
425                 if (!tdb_pwrite_all(tdb->fd, buf, n, off)) {
426                         tdb->ecode = TDB_ERR_IO;
427                         tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
428                                  "fill write failed: giving up!\n");
429                         return -1;
430                 }
431                 len -= n;
432                 off += n;
433         }
434         return 0;
435 }
436
437 /* expand a file.  we prefer to use ftruncate, as that is what posix
438   says to use for mmap expansion */
439 static int tdb_expand_file(struct tdb_context *tdb, tdb_len_t addition)
440 {
441         char buf[8192];
442
443         if (tdb->read_only) {
444                 tdb->ecode = TDB_ERR_RDONLY;
445                 return -1;
446         }
447
448         if (tdb->flags & TDB_INTERNAL) {
449                 char *new = realloc(tdb->map_ptr, tdb->map_size + addition);
450                 if (!new) {
451                         tdb->ecode = TDB_ERR_OOM;
452                         return -1;
453                 }
454                 tdb->map_ptr = new;
455                 tdb->map_size += addition;
456         } else {
457                 /* Unmap before trying to write; old TDB claimed OpenBSD had
458                  * problem with this otherwise. */
459                 tdb_munmap(tdb);
460
461                 /* If this fails, we try to fill anyway. */
462                 if (ftruncate(tdb->fd, tdb->map_size + addition))
463                         ;
464
465                 /* now fill the file with something. This ensures that the
466                    file isn't sparse, which would be very bad if we ran out of
467                    disk. This must be done with write, not via mmap */
468                 memset(buf, 0x43, sizeof(buf));
469                 if (fill(tdb, buf, sizeof(buf), tdb->map_size, addition) == -1)
470                         return -1;
471                 tdb->map_size += addition;
472                 tdb_mmap(tdb);
473         }
474         return 0;
475 }
476
477 const void *tdb_access_read(struct tdb_context *tdb,
478                             tdb_off_t off, tdb_len_t len, bool convert)
479 {
480         const void *ret = NULL;
481
482         if (likely(!(tdb->flags & TDB_CONVERT)))
483                 ret = tdb_direct(tdb, off, len);
484
485         if (!ret) {
486                 ret = tdb_alloc_read(tdb, off, len);
487                 if (convert)
488                         tdb_convert(tdb, (void *)ret, len);
489         }
490         return ret;
491 }
492
493 void tdb_access_release(struct tdb_context *tdb, const void *p)
494 {
495         if (!tdb->map_ptr
496             || (char *)p < (char *)tdb->map_ptr
497             || (char *)p >= (char *)tdb->map_ptr + tdb->map_size)
498                 free((void *)p);
499 }
500
501 #if 0
502 /* write a lump of data at a specified offset */
503 static int tdb_write(struct tdb_context *tdb, tdb_off_t off, 
504                      const void *buf, tdb_len_t len)
505 {
506         if (len == 0) {
507                 return 0;
508         }
509
510         if (tdb->read_only || tdb->traverse_read) {
511                 tdb->ecode = TDB_ERR_RDONLY;
512                 return -1;
513         }
514
515         if (tdb->methods->tdb_oob(tdb, off + len, 0) != 0)
516                 return -1;
517
518         if (tdb->map_ptr) {
519                 memcpy(off + (char *)tdb->map_ptr, buf, len);
520         } else {
521                 ssize_t written = pwrite(tdb->fd, buf, len, off);
522                 if ((written != (ssize_t)len) && (written != -1)) {
523                         /* try once more */
524                         tdb->ecode = TDB_ERR_IO;
525                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_write: wrote only "
526                                  "%d of %d bytes at %d, trying once more\n",
527                                  (int)written, len, off));
528                         written = pwrite(tdb->fd, (const char *)buf+written,
529                                          len-written,
530                                          off+written);
531                 }
532                 if (written == -1) {
533                         /* Ensure ecode is set for log fn. */
534                         tdb->ecode = TDB_ERR_IO;
535                         TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_write failed at %d "
536                                  "len=%d (%s)\n", off, len, strerror(errno)));
537                         return -1;
538                 } else if (written != (ssize_t)len) {
539                         tdb->ecode = TDB_ERR_IO;
540                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_write: failed to "
541                                  "write %d bytes at %d in two attempts\n",
542                                  len, off));
543                         return -1;
544                 }
545         }
546         return 0;
547 }
548
549
550
551 /*
552   do an unlocked scan of the hash table heads to find the next non-zero head. The value
553   will then be confirmed with the lock held
554 */              
555 static void tdb_next_hash_chain(struct tdb_context *tdb, uint32_t *chain)
556 {
557         uint32_t h = *chain;
558         if (tdb->map_ptr) {
559                 for (;h < tdb->header.hash_size;h++) {
560                         if (0 != *(uint32_t *)(TDB_HASH_TOP(h) + (unsigned char *)tdb->map_ptr)) {
561                                 break;
562                         }
563                 }
564         } else {
565                 uint32_t off=0;
566                 for (;h < tdb->header.hash_size;h++) {
567                         if (tdb_ofs_read(tdb, TDB_HASH_TOP(h), &off) != 0 || off != 0) {
568                                 break;
569                         }
570                 }
571         }
572         (*chain) = h;
573 }
574
575 /* read/write a tdb_off_t */
576 int tdb_ofs_read(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d)
577 {
578         return tdb->methods->tdb_read(tdb, offset, (char*)d, sizeof(*d), DOCONV());
579 }
580
581 int tdb_ofs_write(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d)
582 {
583         tdb_off_t off = *d;
584         return tdb->methods->tdb_write(tdb, offset, CONVERT(off), sizeof(*d));
585 }
586
587
588 /* read/write a record */
589 int tdb_rec_read(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
590 {
591         if (tdb->methods->tdb_read(tdb, offset, rec, sizeof(*rec),DOCONV()) == -1)
592                 return -1;
593         if (TDB_BAD_MAGIC(rec)) {
594                 /* Ensure ecode is set for log fn. */
595                 tdb->ecode = TDB_ERR_CORRUPT;
596                 TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_rec_read bad magic 0x%x at offset=%d\n", rec->magic, offset));
597                 return -1;
598         }
599         return tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0);
600 }
601
602 int tdb_rec_write(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
603 {
604         struct tdb_record r = *rec;
605         return tdb->methods->tdb_write(tdb, offset, CONVERT(r), sizeof(r));
606 }
607 #endif
608
609 static const struct tdb_methods io_methods = {
610         tdb_read,
611         tdb_write,
612         tdb_oob,
613         tdb_expand_file,
614 };
615
616 /*
617   initialise the default methods table
618 */
619 void tdb_io_init(struct tdb_context *tdb)
620 {
621         tdb->methods = &io_methods;
622 }