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