Fix sequence logic bug, and satisfies() logic fix/cleanup.
[ccan] / ccan / tdb / 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    
10      ** NOTE! The following LGPL license applies to the tdb
11      ** library. This does NOT imply that all of Samba is released
12      ** under the LGPL
13    
14    This library is free software; you can redistribute it and/or
15    modify it under the terms of the GNU Lesser General Public
16    License as published by the Free Software Foundation; either
17    version 3 of the License, or (at your option) any later version.
18
19    This library is distributed in the hope that it will be useful,
20    but WITHOUT ANY WARRANTY; without even the implied warranty of
21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
22    Lesser General Public License for more details.
23
24    You should have received a copy of the GNU Lesser General Public
25    License along with this library; if not, see <http://www.gnu.org/licenses/>.
26 */
27
28 #include "tdb_private.h"
29 #ifndef MAX
30 #define MAX(a,b) ((a) > (b) ? (a) : (b))
31 #endif
32
33 /* check for an out of bounds access - if it is out of bounds then
34    see if the database has been expanded by someone else and expand
35    if necessary 
36    note that "len" is the minimum length needed for the db
37 */
38 static int tdb_oob(struct tdb_context *tdb, tdb_off_t len, int probe)
39 {
40         struct stat st;
41         if (len <= tdb->map_size)
42                 return 0;
43         if (tdb->flags & TDB_INTERNAL) {
44                 if (!probe) {
45                         /* Ensure ecode is set for log fn. */
46                         tdb->ecode = TDB_ERR_IO;
47                         TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_oob len %d beyond internal malloc size %d\n",
48                                  (int)len, (int)tdb->map_size));
49                 }
50                 return TDB_ERRCODE(TDB_ERR_IO, -1);
51         }
52
53         if (fstat(tdb->fd, &st) == -1) {
54                 return TDB_ERRCODE(TDB_ERR_IO, -1);
55         }
56
57         if (st.st_size < (size_t)len) {
58                 if (!probe) {
59                         /* Ensure ecode is set for log fn. */
60                         tdb->ecode = TDB_ERR_IO;
61                         TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_oob len %d beyond eof at %d\n",
62                                  (int)len, (int)st.st_size));
63                 }
64                 return TDB_ERRCODE(TDB_ERR_IO, -1);
65         }
66
67         /* Unmap, update size, remap */
68         if (tdb_munmap(tdb) == -1)
69                 return TDB_ERRCODE(TDB_ERR_IO, -1);
70         tdb->map_size = st.st_size;
71         tdb_mmap(tdb);
72         return 0;
73 }
74
75 /* write a lump of data at a specified offset */
76 static int tdb_write(struct tdb_context *tdb, tdb_off_t off, 
77                      const void *buf, tdb_len_t len)
78 {
79         if (len == 0) {
80                 return 0;
81         }
82
83         if (tdb->read_only || tdb->traverse_read) {
84                 tdb->ecode = TDB_ERR_RDONLY;
85                 return -1;
86         }
87
88         if (tdb->methods->tdb_oob(tdb, off + len, 0) != 0)
89                 return -1;
90
91         if (tdb->map_ptr) {
92                 memcpy(off + (char *)tdb->map_ptr, buf, len);
93         } else {
94                 ssize_t written = pwrite(tdb->fd, buf, len, off);
95                 if ((written != (ssize_t)len) && (written != -1)) {
96                         /* try once more */
97                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_write: wrote only "
98                                  "%d of %d bytes at %d, trying once more\n",
99                                  (int)written, len, off));
100                         errno = ENOSPC;
101                         written = pwrite(tdb->fd, (const void *)((const char *)buf+written),
102                                          len-written,
103                                          off+written);
104                 }
105                 if (written == -1) {
106                 /* Ensure ecode is set for log fn. */
107                 tdb->ecode = TDB_ERR_IO;
108                         TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_write failed at %d "
109                                  "len=%d (%s)\n", off, len, strerror(errno)));
110                         return TDB_ERRCODE(TDB_ERR_IO, -1);
111                 } else if (written != (ssize_t)len) {
112                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_write: failed to "
113                                  "write %d bytes at %d in two attempts\n",
114                                  len, off));
115                         errno = ENOSPC;
116                 return TDB_ERRCODE(TDB_ERR_IO, -1);
117         }
118         }
119         return 0;
120 }
121
122 /* Endian conversion: we only ever deal with 4 byte quantities */
123 void *tdb_convert(void *buf, uint32_t size)
124 {
125         uint32_t i, *p = (uint32_t *)buf;
126         for (i = 0; i < size / 4; i++)
127                 p[i] = TDB_BYTEREV(p[i]);
128         return buf;
129 }
130
131
132 /* read a lump of data at a specified offset, maybe convert */
133 static int tdb_read(struct tdb_context *tdb, tdb_off_t off, void *buf, 
134                     tdb_len_t len, int cv)
135 {
136         if (tdb->methods->tdb_oob(tdb, off + len, 0) != 0) {
137                 return -1;
138         }
139
140         if (tdb->map_ptr) {
141                 memcpy(buf, off + (char *)tdb->map_ptr, len);
142         } else {
143                 ssize_t ret = pread(tdb->fd, buf, len, off);
144                 if (ret != (ssize_t)len) {
145                         /* Ensure ecode is set for log fn. */
146                         tdb->ecode = TDB_ERR_IO;
147                         TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_read failed at %d "
148                                  "len=%d ret=%d (%s) map_size=%d\n",
149                                  (int)off, (int)len, (int)ret, strerror(errno),
150                                  (int)tdb->map_size));
151                         return TDB_ERRCODE(TDB_ERR_IO, -1);
152                 }
153         }
154         if (cv) {
155                 tdb_convert(buf, len);
156         }
157         return 0;
158 }
159
160
161
162 /*
163   do an unlocked scan of the hash table heads to find the next non-zero head. The value
164   will then be confirmed with the lock held
165 */              
166 static void tdb_next_hash_chain(struct tdb_context *tdb, uint32_t *chain)
167 {
168         uint32_t h = *chain;
169         if (tdb->map_ptr) {
170                 for (;h < tdb->header.hash_size;h++) {
171                         if (0 != *(uint32_t *)(TDB_HASH_TOP(h) + (unsigned char *)tdb->map_ptr)) {
172                                 break;
173                         }
174                 }
175         } else {
176                 uint32_t off=0;
177                 for (;h < tdb->header.hash_size;h++) {
178                         if (tdb_ofs_read(tdb, TDB_HASH_TOP(h), &off) != 0 || off != 0) {
179                                 break;
180                         }
181                 }
182         }
183         (*chain) = h;
184 }
185
186
187 int tdb_munmap(struct tdb_context *tdb)
188 {
189         if (tdb->flags & TDB_INTERNAL)
190                 return 0;
191
192 #if HAVE_MMAP
193         if (tdb->map_ptr) {
194                 int ret = munmap(tdb->map_ptr, tdb->map_size);
195                 if (ret != 0)
196                         return ret;
197         }
198 #endif
199         tdb->map_ptr = NULL;
200         return 0;
201 }
202
203 void tdb_mmap(struct tdb_context *tdb)
204 {
205         if (tdb->flags & TDB_INTERNAL)
206                 return;
207
208 #if HAVE_MMAP
209         if (!(tdb->flags & TDB_NOMMAP)) {
210                 tdb->map_ptr = mmap(NULL, tdb->map_size, 
211                                     PROT_READ|(tdb->read_only? 0:PROT_WRITE), 
212                                     MAP_SHARED, tdb->fd, 0);
213
214                 /*
215                  * NB. When mmap fails it returns MAP_FAILED *NOT* NULL !!!!
216                  */
217
218                 if (tdb->map_ptr == MAP_FAILED) {
219                         tdb->map_ptr = NULL;
220                         TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_mmap failed for size %d (%s)\n", 
221                                  tdb->map_size, strerror(errno)));
222                 }
223         } else {
224                 tdb->map_ptr = NULL;
225         }
226 #else
227         tdb->map_ptr = NULL;
228 #endif
229 }
230
231 /* expand a file.  we prefer to use ftruncate, as that is what posix
232   says to use for mmap expansion */
233 static int tdb_expand_file(struct tdb_context *tdb, tdb_off_t size, tdb_off_t addition)
234 {
235         char buf[8192];
236
237         if (tdb->read_only || tdb->traverse_read) {
238                 tdb->ecode = TDB_ERR_RDONLY;
239                 return -1;
240         }
241
242         if (ftruncate(tdb->fd, size+addition) == -1) {
243                 char b = 0;
244                 ssize_t written = pwrite(tdb->fd,  &b, 1, (size+addition) - 1);
245                 if (written == 0) {
246                         /* try once more, potentially revealing errno */
247                         written = pwrite(tdb->fd,  &b, 1, (size+addition) - 1);
248                 }
249                 if (written == 0) {
250                         /* again - give up, guessing errno */
251                         errno = ENOSPC;
252                 }
253                 if (written != 1) {
254                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "expand_file to %d failed (%s)\n", 
255                                  size+addition, strerror(errno)));
256                         return -1;
257                 }
258         }
259
260         /* now fill the file with something. This ensures that the
261            file isn't sparse, which would be very bad if we ran out of
262            disk. This must be done with write, not via mmap */
263         memset(buf, TDB_PAD_BYTE, sizeof(buf));
264         while (addition) {
265                 size_t n = addition>sizeof(buf)?sizeof(buf):addition;
266                 ssize_t written = pwrite(tdb->fd, buf, n, size);
267                 if (written == 0) {
268                         /* prevent infinite loops: try _once_ more */
269                         written = pwrite(tdb->fd, buf, n, size);
270                 }
271                 if (written == 0) {
272                         /* give up, trying to provide a useful errno */
273                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "expand_file write "
274                                 "returned 0 twice: giving up!\n"));
275                         errno = ENOSPC;
276                         return -1;
277                 } else if (written == -1) {
278                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "expand_file write of "
279                                  "%d bytes failed (%s)\n", (int)n,
280                                  strerror(errno)));
281                         return -1;
282                 } else if (written != n) {
283                         TDB_LOG((tdb, TDB_DEBUG_WARNING, "expand_file: wrote "
284                                  "only %d of %d bytes - retrying\n", (int)written,
285                                  (int)n));
286                 }
287                 addition -= written;
288                 size += written;
289         }
290         return 0;
291 }
292
293
294 /* expand the database at least size bytes by expanding the underlying
295    file and doing the mmap again if necessary */
296 int tdb_expand(struct tdb_context *tdb, tdb_off_t size)
297 {
298         struct list_struct rec;
299         tdb_off_t offset, new_size;     
300
301         if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
302                 TDB_LOG((tdb, TDB_DEBUG_ERROR, "lock failed in tdb_expand\n"));
303                 return -1;
304         }
305
306         /* must know about any previous expansions by another process */
307         tdb->methods->tdb_oob(tdb, tdb->map_size + 1, 1);
308
309         /* always make room for at least 100 more records, and at
310            least 25% more space. Round the database up to a multiple
311            of the page size */
312         new_size = MAX(tdb->map_size + size*100, tdb->map_size * 1.25);
313         size = TDB_ALIGN(new_size, tdb->page_size) - tdb->map_size;
314
315         if (!(tdb->flags & TDB_INTERNAL))
316                 tdb_munmap(tdb);
317
318         /*
319          * We must ensure the file is unmapped before doing this
320          * to ensure consistency with systems like OpenBSD where
321          * writes and mmaps are not consistent.
322          */
323
324         /* expand the file itself */
325         if (!(tdb->flags & TDB_INTERNAL)) {
326                 if (tdb->methods->tdb_expand_file(tdb, tdb->map_size, size) != 0)
327                         goto fail;
328         }
329
330         tdb->map_size += size;
331
332         if (tdb->flags & TDB_INTERNAL) {
333                 char *new_map_ptr = (char *)realloc(tdb->map_ptr,
334                                                     tdb->map_size);
335                 if (!new_map_ptr) {
336                         tdb->map_size -= size;
337                         goto fail;
338                 }
339                 tdb->map_ptr = new_map_ptr;
340         } else {
341                 /*
342                  * We must ensure the file is remapped before adding the space
343                  * to ensure consistency with systems like OpenBSD where
344                  * writes and mmaps are not consistent.
345                  */
346
347                 /* We're ok if the mmap fails as we'll fallback to read/write */
348                 tdb_mmap(tdb);
349         }
350
351         /* form a new freelist record */
352         memset(&rec,'\0',sizeof(rec));
353         rec.rec_len = size - sizeof(rec);
354
355         /* link it into the free list */
356         offset = tdb->map_size - size;
357         if (tdb_free(tdb, offset, &rec) == -1)
358                 goto fail;
359
360         tdb_unlock(tdb, -1, F_WRLCK);
361         return 0;
362  fail:
363         tdb_unlock(tdb, -1, F_WRLCK);
364         return -1;
365 }
366
367 /* read/write a tdb_off_t */
368 int tdb_ofs_read(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d)
369 {
370         return tdb->methods->tdb_read(tdb, offset, (char*)d, sizeof(*d), DOCONV());
371 }
372
373 int tdb_ofs_write(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d)
374 {
375         tdb_off_t off = *d;
376         return tdb->methods->tdb_write(tdb, offset, CONVERT(off), sizeof(*d));
377 }
378
379
380 /* read a lump of data, allocating the space for it */
381 unsigned char *tdb_alloc_read(struct tdb_context *tdb, tdb_off_t offset, tdb_len_t len)
382 {
383         unsigned char *buf;
384
385         /* some systems don't like zero length malloc */
386         if (!(buf = (unsigned char *)malloc(len ? len : 1))) {
387                 /* Ensure ecode is set for log fn. */
388                 tdb->ecode = TDB_ERR_OOM;
389                 TDB_LOG((tdb, TDB_DEBUG_ERROR,"tdb_alloc_read malloc failed len=%d (%s)\n",
390                            len, strerror(errno)));
391                 return TDB_ERRCODE(TDB_ERR_OOM, buf);
392         }
393         if (tdb->methods->tdb_read(tdb, offset, buf, len, 0) == -1) {
394                 SAFE_FREE(buf);
395                 return NULL;
396         }
397         return buf;
398 }
399
400 /* Give a piece of tdb data to a parser */
401
402 int tdb_parse_data(struct tdb_context *tdb, TDB_DATA key,
403                    tdb_off_t offset, tdb_len_t len,
404                    int (*parser)(TDB_DATA key, TDB_DATA data,
405                                  void *private_data),
406                    void *private_data)
407 {
408         TDB_DATA data;
409         int result;
410
411         data.dsize = len;
412
413         if ((tdb->transaction == NULL) && (tdb->map_ptr != NULL)) {
414                 /*
415                  * Optimize by avoiding the malloc/memcpy/free, point the
416                  * parser directly at the mmap area.
417                  */
418                 if (tdb->methods->tdb_oob(tdb, offset+len, 0) != 0) {
419                         return -1;
420                 }
421                 data.dptr = offset + (unsigned char *)tdb->map_ptr;
422                 return parser(key, data, private_data);
423         }
424
425         if (!(data.dptr = tdb_alloc_read(tdb, offset, len))) {
426                 return -1;
427         }
428
429         result = parser(key, data, private_data);
430         free(data.dptr);
431         return result;
432 }
433
434 /* read/write a record */
435 int tdb_rec_read(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec)
436 {
437         if (tdb->methods->tdb_read(tdb, offset, rec, sizeof(*rec),DOCONV()) == -1)
438                 return -1;
439         if (TDB_BAD_MAGIC(rec)) {
440                 /* Ensure ecode is set for log fn. */
441                 tdb->ecode = TDB_ERR_CORRUPT;
442                 TDB_LOG((tdb, TDB_DEBUG_FATAL,"tdb_rec_read bad magic 0x%x at offset=%d\n", rec->magic, offset));
443                 return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
444         }
445         return tdb->methods->tdb_oob(tdb, rec->next+sizeof(*rec), 0);
446 }
447
448 int tdb_rec_write(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec)
449 {
450         struct list_struct r = *rec;
451         return tdb->methods->tdb_write(tdb, offset, CONVERT(r), sizeof(r));
452 }
453
454 static const struct tdb_methods io_methods = {
455         tdb_read,
456         tdb_write,
457         tdb_next_hash_chain,
458         tdb_oob,
459         tdb_expand_file,
460         tdb_brlock
461 };
462
463 /*
464   initialise the default methods table
465 */
466 void tdb_io_init(struct tdb_context *tdb)
467 {
468         tdb->methods = &io_methods;
469 }