52e2d633b0a39a56c092485410945b4888db6a52
[ira/wip.git] / source / lib / tdb / common / tdb.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 2 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, write to the Free Software
26    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
27 */
28
29 #include "tdb_private.h"
30
31 TDB_DATA tdb_null;
32
33 /*
34   increment the tdb sequence number if the tdb has been opened using
35   the TDB_SEQNUM flag
36 */
37 static void tdb_increment_seqnum(struct tdb_context *tdb)
38 {
39         tdb_off_t seqnum=0;
40         
41         if (!(tdb->flags & TDB_SEQNUM)) {
42                 return;
43         }
44
45         if (tdb_brlock(tdb, TDB_SEQNUM_OFS, F_WRLCK, F_SETLKW, 1, 1) != 0) {
46                 return;
47         }
48
49         /* we ignore errors from this, as we have no sane way of
50            dealing with them.
51         */
52         tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum);
53         seqnum++;
54         tdb_ofs_write(tdb, TDB_SEQNUM_OFS, &seqnum);
55
56         tdb_brlock(tdb, TDB_SEQNUM_OFS, F_UNLCK, F_SETLKW, 1, 1);
57 }
58
59
60 /* Returns 0 on fail.  On success, return offset of record, and fills
61    in rec */
62 static tdb_off_t tdb_find(struct tdb_context *tdb, TDB_DATA key, u32 hash,
63                         struct list_struct *r)
64 {
65         tdb_off_t rec_ptr;
66         
67         /* read in the hash top */
68         if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
69                 return 0;
70
71         /* keep looking until we find the right record */
72         while (rec_ptr) {
73                 if (tdb_rec_read(tdb, rec_ptr, r) == -1)
74                         return 0;
75
76                 if (!TDB_DEAD(r) && hash==r->full_hash && key.dsize==r->key_len) {
77                         unsigned char *k;
78                         /* a very likely hit - read the key */
79                         k = tdb_alloc_read(tdb, rec_ptr + sizeof(*r), 
80                                            r->key_len);
81                         if (!k)
82                                 return 0;
83
84                         if (memcmp(key.dptr, k, key.dsize) == 0) {
85                                 SAFE_FREE(k);
86                                 return rec_ptr;
87                         }
88                         SAFE_FREE(k);
89                 }
90                 rec_ptr = r->next;
91         }
92         return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
93 }
94
95 /* As tdb_find, but if you succeed, keep the lock */
96 tdb_off_t tdb_find_lock_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash, int locktype,
97                            struct list_struct *rec)
98 {
99         u32 rec_ptr;
100
101         if (tdb_lock(tdb, BUCKET(hash), locktype) == -1)
102                 return 0;
103         if (!(rec_ptr = tdb_find(tdb, key, hash, rec)))
104                 tdb_unlock(tdb, BUCKET(hash), locktype);
105         return rec_ptr;
106 }
107
108
109 /* update an entry in place - this only works if the new data size
110    is <= the old data size and the key exists.
111    on failure return -1.
112 */
113 static int tdb_update_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash, TDB_DATA dbuf)
114 {
115         struct list_struct rec;
116         tdb_off_t rec_ptr;
117
118         /* find entry */
119         if (!(rec_ptr = tdb_find(tdb, key, hash, &rec)))
120                 return -1;
121
122         /* must be long enough key, data and tailer */
123         if (rec.rec_len < key.dsize + dbuf.dsize + sizeof(tdb_off_t)) {
124                 tdb->ecode = TDB_SUCCESS; /* Not really an error */
125                 return -1;
126         }
127
128         if (tdb->methods->tdb_write(tdb, rec_ptr + sizeof(rec) + rec.key_len,
129                       dbuf.dptr, dbuf.dsize) == -1)
130                 return -1;
131
132         if (dbuf.dsize != rec.data_len) {
133                 /* update size */
134                 rec.data_len = dbuf.dsize;
135                 return tdb_rec_write(tdb, rec_ptr, &rec);
136         }
137  
138         return 0;
139 }
140
141 /* find an entry in the database given a key */
142 /* If an entry doesn't exist tdb_err will be set to
143  * TDB_ERR_NOEXIST. If a key has no data attached
144  * then the TDB_DATA will have zero length but
145  * a non-zero pointer
146  */
147 TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
148 {
149         tdb_off_t rec_ptr;
150         struct list_struct rec;
151         TDB_DATA ret;
152         u32 hash;
153
154         /* find which hash bucket it is in */
155         hash = tdb->hash_fn(&key);
156         if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec)))
157                 return tdb_null;
158
159         ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len,
160                                   rec.data_len);
161         ret.dsize = rec.data_len;
162         tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
163         return ret;
164 }
165
166 /* check if an entry in the database exists 
167
168    note that 1 is returned if the key is found and 0 is returned if not found
169    this doesn't match the conventions in the rest of this module, but is
170    compatible with gdbm
171 */
172 static int tdb_exists_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash)
173 {
174         struct list_struct rec;
175         
176         if (tdb_find_lock_hash(tdb, key, hash, F_RDLCK, &rec) == 0)
177                 return 0;
178         tdb_unlock(tdb, BUCKET(rec.full_hash), F_RDLCK);
179         return 1;
180 }
181
182 int tdb_exists(struct tdb_context *tdb, TDB_DATA key)
183 {
184         u32 hash = tdb->hash_fn(&key);
185         return tdb_exists_hash(tdb, key, hash);
186 }
187
188 /* actually delete an entry in the database given the offset */
189 int tdb_do_delete(struct tdb_context *tdb, tdb_off_t rec_ptr, struct list_struct*rec)
190 {
191         tdb_off_t last_ptr, i;
192         struct list_struct lastrec;
193
194         if (tdb->read_only || tdb->traverse_read) return -1;
195
196         if (tdb_write_lock_record(tdb, rec_ptr) == -1) {
197                 /* Someone traversing here: mark it as dead */
198                 rec->magic = TDB_DEAD_MAGIC;
199                 return tdb_rec_write(tdb, rec_ptr, rec);
200         }
201         if (tdb_write_unlock_record(tdb, rec_ptr) != 0)
202                 return -1;
203
204         /* find previous record in hash chain */
205         if (tdb_ofs_read(tdb, TDB_HASH_TOP(rec->full_hash), &i) == -1)
206                 return -1;
207         for (last_ptr = 0; i != rec_ptr; last_ptr = i, i = lastrec.next)
208                 if (tdb_rec_read(tdb, i, &lastrec) == -1)
209                         return -1;
210
211         /* unlink it: next ptr is at start of record. */
212         if (last_ptr == 0)
213                 last_ptr = TDB_HASH_TOP(rec->full_hash);
214         if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1)
215                 return -1;
216
217         /* recover the space */
218         if (tdb_free(tdb, rec_ptr, rec) == -1)
219                 return -1;
220         return 0;
221 }
222
223 /* delete an entry in the database given a key */
224 static int tdb_delete_hash(struct tdb_context *tdb, TDB_DATA key, u32 hash)
225 {
226         tdb_off_t rec_ptr;
227         struct list_struct rec;
228         int ret;
229
230         if (!(rec_ptr = tdb_find_lock_hash(tdb, key, hash, F_WRLCK, &rec)))
231                 return -1;
232         ret = tdb_do_delete(tdb, rec_ptr, &rec);
233
234         if (ret == 0) {
235                 tdb_increment_seqnum(tdb);
236         }
237
238         if (tdb_unlock(tdb, BUCKET(rec.full_hash), F_WRLCK) != 0)
239                 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_delete: WARNING tdb_unlock failed!\n"));
240         return ret;
241 }
242
243 int tdb_delete(struct tdb_context *tdb, TDB_DATA key)
244 {
245         u32 hash = tdb->hash_fn(&key);
246         return tdb_delete_hash(tdb, key, hash);
247 }
248
249 /* store an element in the database, replacing any existing element
250    with the same key 
251
252    return 0 on success, -1 on failure
253 */
254 int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
255 {
256         struct list_struct rec;
257         u32 hash;
258         tdb_off_t rec_ptr;
259         char *p = NULL;
260         int ret = 0;
261
262         if (tdb->read_only || tdb->traverse_read) {
263                 tdb->ecode = TDB_ERR_RDONLY;
264                 return -1;
265         }
266
267         /* find which hash bucket it is in */
268         hash = tdb->hash_fn(&key);
269         if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
270                 return -1;
271
272         /* check for it existing, on insert. */
273         if (flag == TDB_INSERT) {
274                 if (tdb_exists_hash(tdb, key, hash)) {
275                         tdb->ecode = TDB_ERR_EXISTS;
276                         goto fail;
277                 }
278         } else {
279                 /* first try in-place update, on modify or replace. */
280                 if (tdb_update_hash(tdb, key, hash, dbuf) == 0)
281                         goto out;
282                 if (tdb->ecode == TDB_ERR_NOEXIST &&
283                     flag == TDB_MODIFY) {
284                         /* if the record doesn't exist and we are in TDB_MODIFY mode then
285                          we should fail the store */
286                         goto fail;
287                 }
288         }
289         /* reset the error code potentially set by the tdb_update() */
290         tdb->ecode = TDB_SUCCESS;
291
292         /* delete any existing record - if it doesn't exist we don't
293            care.  Doing this first reduces fragmentation, and avoids
294            coalescing with `allocated' block before it's updated. */
295         if (flag != TDB_INSERT)
296                 tdb_delete_hash(tdb, key, hash);
297
298         /* Copy key+value *before* allocating free space in case malloc
299            fails and we are left with a dead spot in the tdb. */
300
301         if (!(p = (char *)malloc(key.dsize + dbuf.dsize))) {
302                 tdb->ecode = TDB_ERR_OOM;
303                 goto fail;
304         }
305
306         memcpy(p, key.dptr, key.dsize);
307         if (dbuf.dsize)
308                 memcpy(p+key.dsize, dbuf.dptr, dbuf.dsize);
309
310         /* we have to allocate some space */
311         if (!(rec_ptr = tdb_allocate(tdb, key.dsize + dbuf.dsize, &rec)))
312                 goto fail;
313
314         /* Read hash top into next ptr */
315         if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec.next) == -1)
316                 goto fail;
317
318         rec.key_len = key.dsize;
319         rec.data_len = dbuf.dsize;
320         rec.full_hash = hash;
321         rec.magic = TDB_MAGIC;
322
323         /* write out and point the top of the hash chain at it */
324         if (tdb_rec_write(tdb, rec_ptr, &rec) == -1
325             || tdb->methods->tdb_write(tdb, rec_ptr+sizeof(rec), p, key.dsize+dbuf.dsize)==-1
326             || tdb_ofs_write(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1) {
327                 /* Need to tdb_unallocate() here */
328                 goto fail;
329         }
330
331         tdb_increment_seqnum(tdb);
332
333  out:
334         SAFE_FREE(p); 
335         tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
336         return ret;
337 fail:
338         ret = -1;
339         goto out;
340 }
341
342
343 /* Append to an entry. Create if not exist. */
344 int tdb_append(struct tdb_context *tdb, TDB_DATA key, TDB_DATA new_dbuf)
345 {
346         u32 hash;
347         TDB_DATA dbuf;
348         int ret = -1;
349
350         /* find which hash bucket it is in */
351         hash = tdb->hash_fn(&key);
352         if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
353                 return -1;
354
355         dbuf = tdb_fetch(tdb, key);
356
357         if (dbuf.dptr == NULL) {
358                 dbuf.dptr = malloc(new_dbuf.dsize);
359         } else {
360                 dbuf.dptr = realloc(dbuf.dptr, dbuf.dsize + new_dbuf.dsize);
361         }
362
363         if (dbuf.dptr == NULL) {
364                 tdb->ecode = TDB_ERR_OOM;
365                 goto failed;
366         }
367
368         memcpy(dbuf.dptr + dbuf.dsize, new_dbuf.dptr, new_dbuf.dsize);
369         dbuf.dsize += new_dbuf.dsize;
370
371         ret = tdb_store(tdb, key, dbuf, 0);
372         
373 failed:
374         tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
375         SAFE_FREE(dbuf.dptr);
376         return ret;
377 }
378
379
380 /*
381   return the name of the current tdb file
382   useful for external logging functions
383 */
384 const char *tdb_name(struct tdb_context *tdb)
385 {
386         return tdb->name;
387 }
388
389 /*
390   return the underlying file descriptor being used by tdb, or -1
391   useful for external routines that want to check the device/inode
392   of the fd
393 */
394 int tdb_fd(struct tdb_context *tdb)
395 {
396         return tdb->fd;
397 }
398
399 /*
400   return the current logging function
401   useful for external tdb routines that wish to log tdb errors
402 */
403 tdb_log_func tdb_log_fn(struct tdb_context *tdb)
404 {
405         return tdb->log.log_fn;
406 }
407
408
409 /*
410   get the tdb sequence number. Only makes sense if the writers opened
411   with TDB_SEQNUM set. Note that this sequence number will wrap quite
412   quickly, so it should only be used for a 'has something changed'
413   test, not for code that relies on the count of the number of changes
414   made. If you want a counter then use a tdb record.
415
416   The aim of this sequence number is to allow for a very lightweight
417   test of a possible tdb change.
418 */
419 int tdb_get_seqnum(struct tdb_context *tdb)
420 {
421         tdb_off_t seqnum=0;
422
423         tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum);
424         return seqnum;
425 }