e0db60a4f88a20ec277b2c6ca2e07c1499446b53
[dragonfly.git] / sys / vfs / hammer / hammer_object.c
1 /*
2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
3  * 
4  * This code is derived from software contributed to The DragonFly Project
5  * by Matthew Dillon <dillon@backplane.com>
6  * 
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  * 3. Neither the name of The DragonFly Project nor the names of its
18  *    contributors may be used to endorse or promote products derived
19  *    from this software without specific, prior written permission.
20  * 
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  * 
34  * $DragonFly: src/sys/vfs/hammer/hammer_object.c,v 1.11 2007/12/30 00:47:22 dillon Exp $
35  */
36
37 #include "hammer.h"
38
39 static int hammer_mem_add(hammer_transaction_t trans,
40                              hammer_record_t record);
41 static int hammer_mem_lookup(hammer_cursor_t cursor, hammer_inode_t ip);
42 static int hammer_mem_first(hammer_cursor_t cursor, hammer_inode_t ip);
43 static void hammer_free_mem_record(hammer_record_t record);
44
45 /*
46  * Red-black tree support.
47  */
48 static int
49 hammer_rec_rb_compare(hammer_record_t rec1, hammer_record_t rec2)
50 {
51         if (rec1->rec.base.base.rec_type < rec2->rec.base.base.rec_type)
52                 return(-1);
53         if (rec1->rec.base.base.rec_type > rec2->rec.base.base.rec_type)
54                 return(1);
55
56         if (rec1->rec.base.base.key < rec2->rec.base.base.key)
57                 return(-1);
58         if (rec1->rec.base.base.key > rec2->rec.base.base.key)
59                 return(1);
60
61         if (rec1->rec.base.base.create_tid < rec2->rec.base.base.create_tid)
62                 return(-1);
63         if (rec1->rec.base.base.create_tid > rec2->rec.base.base.create_tid)
64                 return(1);
65         return(0);
66 }
67
68 static int
69 hammer_rec_compare(hammer_base_elm_t info, hammer_record_t rec)
70 {
71         if (info->rec_type < rec->rec.base.base.rec_type)
72                 return(-3);
73         if (info->rec_type > rec->rec.base.base.rec_type)
74                 return(3);
75
76         if (info->key < rec->rec.base.base.key)
77                 return(-2);
78         if (info->key > rec->rec.base.base.key)
79                 return(2);
80
81         /*
82          * This test has a number of special cases.  create_tid in key1 is
83          * the as-of transction id, and delete_tid in key1 is NOT USED.
84          *
85          * A key1->create_tid of 0 matches any record regardles of when
86          * it was created or destroyed.  0xFFFFFFFFFFFFFFFFULL should be
87          * used to search for the most current state of the object.
88          *
89          * key2->create_tid is a HAMMER record and will never be
90          * 0.   key2->delete_tid is the deletion transaction id or 0 if
91          * the record has not yet been deleted.
92          */
93         if (info->create_tid) {
94                 if (info->create_tid < rec->rec.base.base.create_tid)
95                         return(-1);
96                 if (rec->rec.base.base.delete_tid &&
97                     info->create_tid >= rec->rec.base.base.delete_tid) {
98                         return(1);
99                 }
100         }
101         return(0);
102 }
103
104 /*
105  * RB_SCAN comparison code for hammer_mem_first().  The argument order
106  * is reversed so the comparison result has to be negated.  key_beg and
107  * key_end are both range-inclusive.
108  *
109  * The creation timestamp can cause hammer_rec_compare() to return -1 or +1.
110  * These do not stop the scan.
111  *
112  * Localized deletions are not cached in-memory.
113  */
114 static
115 int
116 hammer_rec_scan_cmp(hammer_record_t rec, void *data)
117 {
118         hammer_cursor_t cursor = data;
119         int r;
120
121         r = hammer_rec_compare(&cursor->key_beg, rec);
122         if (r > 1)
123                 return(-1);
124         if (r == 0)
125                 return(0);
126         r = hammer_rec_compare(&cursor->key_end, rec);
127         if (r < -1)
128                 return(1);
129         return(0);
130 }
131
132 RB_GENERATE(hammer_rec_rb_tree, hammer_record, rb_node, hammer_rec_rb_compare);
133 RB_GENERATE_XLOOKUP(hammer_rec_rb_tree, INFO, hammer_record, rb_node,
134                     hammer_rec_compare, hammer_base_elm_t);
135
136 /*
137  * Allocate a record for the caller to finish filling in.  The record is
138  * returned referenced and locked.
139  */
140 hammer_record_t
141 hammer_alloc_mem_record(hammer_inode_t ip)
142 {
143         hammer_record_t record;
144
145         record = kmalloc(sizeof(*record), M_HAMMER, M_WAITOK|M_ZERO);
146         record->ip = ip;
147         hammer_ref(&record->lock);
148         hammer_lock_ex(&record->lock);
149         return (record);
150 }
151
152 /*
153  * Release a memory record.  If the record was marked for defered deletion,
154  * and no references remain, the record is physically destroyed.
155  */
156 void
157 hammer_rel_mem_record(struct hammer_record **recordp)
158 {
159         hammer_record_t rec;
160
161         if ((rec = *recordp) != NULL) {
162                 hammer_unref(&rec->lock);
163                 if (rec->lock.refs == 0) {
164                         if (rec->flags & HAMMER_RECF_DELETED)
165                                 hammer_free_mem_record(rec);
166                 }
167                 *recordp = NULL;
168         }
169 }
170
171 /*
172  * Drop a locked hammer in-memory record.  This function unlocks and
173  * dereferences the record.  If delete != 0 the record is marked for
174  * deletion.  Physical deletion only occurs when the last reference goes
175  * away.
176  */
177 void
178 hammer_drop_mem_record(hammer_record_t rec, int delete)
179 {
180         if (delete)
181                 rec->flags |= HAMMER_RECF_DELETED;
182         hammer_unlock(&rec->lock);
183         hammer_rel_mem_record(&rec);
184 }
185
186 /*
187  * Free a record.  Clean the structure up even though we are throwing it
188  * away as a sanity check.  The actual free operation is delayed while
189  * the record is referenced.  However, the record is removed from the RB
190  * tree immediately.
191  */
192 static void
193 hammer_free_mem_record(hammer_record_t record)
194 {
195         if (record->flags & HAMMER_RECF_ONRBTREE) {
196                 RB_REMOVE(hammer_rec_rb_tree, &record->ip->rec_tree, record);
197                 record->flags &= ~HAMMER_RECF_ONRBTREE;
198         }
199         if (record->lock.refs) {
200                 record->flags |= HAMMER_RECF_DELETED;
201                 return;
202         }
203         if (record->flags & HAMMER_RECF_ALLOCDATA) {
204                 kfree(record->data, M_HAMMER);
205                 record->flags &= ~HAMMER_RECF_ALLOCDATA;
206         }
207         record->data = NULL;
208         kfree(record, M_HAMMER);
209 }
210
211 /*
212  * Lookup an in-memory record given the key specified in the cursor.  Works
213  * just like hammer_btree_lookup() but operates on an inode's in-memory
214  * record list.
215  *
216  * The lookup must fail if the record is marked for deferred deletion.
217  */
218 static
219 int
220 hammer_mem_lookup(hammer_cursor_t cursor, hammer_inode_t ip)
221 {
222         int error;
223
224         if (cursor->iprec)
225                 hammer_rel_mem_record(&cursor->iprec);
226         if (cursor->ip) {
227                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
228                                                   &cursor->ip->rec_tree);
229         }
230         cursor->ip = ip;
231         hammer_rec_rb_tree_scan_info_link(&cursor->scan, &ip->rec_tree);
232         cursor->scan.node = NULL;
233         cursor->iprec = hammer_rec_rb_tree_RB_LOOKUP_INFO(
234                                 &ip->rec_tree, &cursor->key_beg);
235         if (cursor->iprec == NULL) {
236                 error = ENOENT;
237         } else {
238                 hammer_ref(&cursor->iprec->lock);
239                 error = 0;
240         }
241         return(error);
242 }
243
244 /*
245  * hammer_mem_first() - locate the first in-memory record matching the
246  * cursor.
247  *
248  * The RB_SCAN function we use is designed as a callback.  We terminate it
249  * (return -1) as soon as we get a match.
250  */
251 static
252 int
253 hammer_rec_scan_callback(hammer_record_t rec, void *data)
254 {
255         hammer_cursor_t cursor = data;
256
257         /*
258          * Skip if not visible due to our as-of TID
259          */
260         if (cursor->key_beg.create_tid) {
261                 if (cursor->key_beg.create_tid < rec->rec.base.base.create_tid)
262                         return(0);
263                 if (rec->rec.base.base.delete_tid &&
264                     cursor->key_beg.create_tid >=
265                      rec->rec.base.base.delete_tid) {
266                         return(0);
267                 }
268         }
269
270         /*
271          * Return the first matching record and stop the scan
272          */
273         if (cursor->iprec == NULL) {
274                 cursor->iprec = rec;
275                 hammer_ref(&rec->lock);
276                 return(-1);
277         }
278         return(0);
279 }
280
281 static
282 int
283 hammer_mem_first(hammer_cursor_t cursor, hammer_inode_t ip)
284 {
285         if (cursor->iprec)
286                 hammer_rel_mem_record(&cursor->iprec);
287         if (cursor->ip) {
288                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
289                                                   &cursor->ip->rec_tree);
290         }
291         cursor->ip = ip;
292         hammer_rec_rb_tree_scan_info_link(&cursor->scan, &ip->rec_tree);
293         cursor->scan.node = NULL;
294         hammer_rec_rb_tree_RB_SCAN(&ip->rec_tree, hammer_rec_scan_cmp,
295                                    hammer_rec_scan_callback, cursor);
296
297         /*
298          * Adjust scan.node and keep it linked into the RB-tree so we can
299          * hold the cursor through third party modifications of the RB-tree.
300          */
301         if (cursor->iprec) {
302                 cursor->scan.node = hammer_rec_rb_tree_RB_NEXT(cursor->iprec);
303                 return(0);
304         }
305         return(ENOENT);
306 }
307
308 void
309 hammer_mem_done(hammer_cursor_t cursor)
310 {
311         if (cursor->ip) {
312                 hammer_rec_rb_tree_scan_info_done(&cursor->scan,
313                                                   &cursor->ip->rec_tree);
314                 cursor->ip = NULL;
315         }
316         if (cursor->iprec)
317                 hammer_rel_mem_record(&cursor->iprec);
318 }
319
320 /************************************************************************
321  *                   HAMMER IN-MEMORY RECORD FUNCTIONS                  *
322  ************************************************************************
323  *
324  * These functions manipulate in-memory records.  Such records typically
325  * exist prior to being committed to disk or indexed via the on-disk B-Tree.
326  */
327
328 /*
329  * Add a directory entry (dip,ncp) which references inode (ip).
330  *
331  * Note that the low 32 bits of the namekey are set temporarily to create
332  * a unique in-memory record, and may be modified a second time when the
333  * record is synchronized to disk.  In particular, the low 32 bits cannot be
334  * all 0's when synching to disk, which is not handled here.
335  */
336 int
337 hammer_ip_add_directory(struct hammer_transaction *trans,
338                      struct hammer_inode *dip, struct namecache *ncp,
339                      struct hammer_inode *ip)
340 {
341         hammer_record_t record;
342         int error;
343         int bytes;
344
345         record = hammer_alloc_mem_record(dip);
346
347         bytes = ncp->nc_nlen;   /* NOTE: terminating \0 is NOT included */
348         if (++trans->hmp->namekey_iterator == 0)
349                 ++trans->hmp->namekey_iterator;
350
351         record->rec.entry.base.base.obj_id = dip->obj_id;
352         record->rec.entry.base.base.key =
353                 hammer_directory_namekey(ncp->nc_name, bytes);
354         record->rec.entry.base.base.key += trans->hmp->namekey_iterator;
355         record->rec.entry.base.base.create_tid = trans->tid;
356         record->rec.entry.base.base.rec_type = HAMMER_RECTYPE_DIRENTRY;
357         record->rec.entry.base.base.obj_type = ip->ino_rec.base.base.obj_type;
358         record->rec.entry.obj_id = ip->obj_id;
359         if (bytes <= sizeof(record->rec.entry.den_name)) {
360                 record->data = (void *)record->rec.entry.den_name;
361                 record->flags |= HAMMER_RECF_EMBEDDED_DATA;
362         } else {
363                 record->data = kmalloc(bytes, M_HAMMER, M_WAITOK);
364                 record->flags |= HAMMER_RECF_ALLOCDATA;
365         }
366         bcopy(ncp->nc_name, record->data, bytes);
367         record->rec.entry.base.data_len = bytes;
368         ++ip->ino_rec.ino_nlinks;
369         hammer_modify_inode(trans, ip,
370                             HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
371         error = hammer_mem_add(trans, record);
372         return(error);
373 }
374
375 /*
376  * Delete the directory entry and update the inode link count.  The
377  * cursor must be seeked to the directory entry record being deleted.
378  *
379  * NOTE: HAMMER_CURSOR_DELETE may not have been set.  XXX remove flag.
380  */
381 int
382 hammer_ip_del_directory(struct hammer_transaction *trans,
383                      hammer_cursor_t cursor, struct hammer_inode *dip,
384                      struct hammer_inode *ip)
385 {
386         int error;
387
388         error = hammer_ip_delete_record(cursor, trans->tid);
389
390         /*
391          * One less link.  The file may still be open in the OS even after
392          * all links have gone away so we don't destroy the inode's data
393          * here.
394          */
395         if (error == 0) {
396                 --ip->ino_rec.ino_nlinks;
397                 hammer_modify_inode(trans, ip,
398                                     HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
399                 if (ip->vp == NULL || (ip->vp->v_flag & VINACTIVE))
400                         hammer_sync_inode(ip, MNT_NOWAIT, 1);
401
402         }
403         return(error);
404 }
405
406 /*
407  * Add a record to an inode.
408  *
409  * The caller must allocate the record with hammer_alloc_mem_record(ip) and
410  * initialize the following additional fields:
411  *
412  * record->rec.entry.base.base.key
413  * record->rec.entry.base.base.rec_type
414  * record->rec.entry.base.base.data_len
415  * record->data         (a copy will be kmalloc'd if not embedded)
416  */
417 int
418 hammer_ip_add_record(struct hammer_transaction *trans, hammer_record_t record)
419 {
420         hammer_inode_t ip = record->ip;
421         int error;
422         int bytes;
423         void *data;
424
425         record->rec.base.base.obj_id = ip->obj_id;
426         record->rec.base.base.create_tid = trans->tid;
427         record->rec.base.base.obj_type = ip->ino_rec.base.base.obj_type;
428         bytes = record->rec.base.data_len;
429
430         if (record->data) {
431                 if ((char *)record->data < (char *)&record->rec ||
432                     (char *)record->data >= (char *)(&record->rec + 1)) {
433                         data = kmalloc(bytes, M_HAMMER, M_WAITOK);
434                         record->flags |= HAMMER_RECF_ALLOCDATA;
435                         bcopy(record->data, data, bytes);
436                         record->data = data;
437                 } else {
438                         record->flags |= HAMMER_RECF_EMBEDDED_DATA;
439                 }
440         }
441         hammer_modify_inode(trans, ip,
442                             HAMMER_INODE_RDIRTY | HAMMER_INODE_TID);
443         error = hammer_mem_add(trans, record);
444         return(error);
445 }
446
447 /*
448  * Sync data from a buffer cache buffer (typically) to the filesystem.  This
449  * is called via the strategy called from a cached data source.  This code
450  * is responsible for actually writing a data record out to the disk.
451  */
452 int
453 hammer_ip_sync_data(hammer_transaction_t trans, hammer_inode_t ip,
454                        int64_t offset, void *data, int bytes,
455                        struct hammer_cursor **spike)
456 {
457         struct hammer_cursor cursor;
458         hammer_record_ondisk_t rec;
459         union hammer_btree_elm elm;
460         void *bdata;
461         int error;
462
463         error = hammer_init_cursor_ip(&cursor, ip);
464         if (error)
465                 return(error);
466         cursor.key_beg.obj_id = ip->obj_id;
467         cursor.key_beg.key = offset + bytes;
468         cursor.key_beg.create_tid = trans->tid;
469         cursor.key_beg.delete_tid = 0;
470         cursor.key_beg.rec_type = HAMMER_RECTYPE_DATA;
471         cursor.flags = HAMMER_CURSOR_INSERT;
472
473         /*
474          * Issue a lookup to position the cursor and locate the cluster
475          */
476         error = hammer_btree_lookup(&cursor);
477         if (error == 0) {
478                 kprintf("hammer_ip_sync_data: duplicate data at (%lld,%d)\n",
479                         offset, bytes);
480                 hammer_print_btree_elm(&cursor.node->ondisk->elms[cursor.index],
481                                        HAMMER_BTREE_TYPE_LEAF, cursor.index);
482                 error = EIO;
483         }
484         if (error != ENOENT)
485                 goto done;
486
487         /*
488          * Allocate record and data space now that we know which cluster
489          * the B-Tree node ended up in.
490          */
491         bdata = hammer_alloc_data(cursor.node->cluster, bytes, &error,
492                                   &cursor.data_buffer);
493         if (bdata == NULL)
494                 goto done;
495         rec = hammer_alloc_record(cursor.node->cluster, &error,
496                                   &cursor.record_buffer);
497         if (rec == NULL)
498                 goto fail1;
499
500         /*
501          * Fill everything in and insert our B-Tree node.
502          */
503         rec->base.base = cursor.key_beg;
504         rec->base.data_crc = crc32(data, bytes);
505         rec->base.rec_id = 0;   /* XXX */
506         rec->base.data_offset = hammer_bclu_offset(cursor.data_buffer, bdata);
507         rec->base.data_len = bytes;
508         hammer_modify_buffer(cursor.record_buffer);
509
510         bcopy(data, bdata, bytes);
511         hammer_modify_buffer(cursor.data_buffer);
512
513         elm.leaf.base = cursor.key_beg;
514         elm.leaf.rec_offset = hammer_bclu_offset(cursor.record_buffer, rec);
515         elm.leaf.data_offset = rec->base.data_offset;
516         elm.leaf.data_len = bytes;
517         elm.leaf.data_crc = rec->base.data_crc;
518
519         error = hammer_btree_insert(&cursor, &elm);
520         if (error == 0)
521                 goto done;
522
523         hammer_free_record_ptr(cursor.record_buffer, rec);
524 fail1:
525         hammer_free_data_ptr(cursor.data_buffer, bdata, bytes);
526 done:
527         /*
528          * If ENOSPC in cluster fill in the spike structure and return
529          * ENOSPC.
530          */
531         if (error == ENOSPC)
532                 hammer_load_spike(&cursor, spike);
533         hammer_done_cursor(&cursor);
534         return(error);
535 }
536
537 /*
538  * Sync an in-memory record to the disk.  this is typically called via fsync
539  * from a cached record source.  This code is responsible for actually
540  * writing a record out to the disk.
541  */
542 int
543 hammer_ip_sync_record(hammer_record_t record, struct hammer_cursor **spike)
544 {
545         struct hammer_cursor cursor;
546         hammer_record_ondisk_t rec;
547         union hammer_btree_elm elm;
548         void *bdata;
549         int error;
550
551         error = hammer_init_cursor_ip(&cursor, record->ip);
552         if (error)
553                 return(error);
554         cursor.key_beg = record->rec.base.base;
555         cursor.flags = HAMMER_CURSOR_INSERT;
556
557         /*
558          * Issue a lookup to position the cursor and locate the cluster.  The
559          * target key should not exist.
560          *
561          * If we run out of space trying to adjust the B-Tree for the
562          * insert, re-lookup without the insert flag so the cursor
563          * is properly positioned for the spike.
564          */
565         error = hammer_btree_lookup(&cursor);
566         if (error == 0) {
567                 kprintf("hammer_ip_sync_record: duplicate rec at (%016llx)\n",
568                         record->rec.base.base.key);
569                 error = EIO;
570         }
571         if (error != ENOENT)
572                 goto done;
573
574         /*
575          * Allocate record and data space now that we know which cluster
576          * the B-Tree node ended up in.
577          */
578         if (record->data == NULL ||
579             (record->flags & HAMMER_RECF_EMBEDDED_DATA)) {
580                 bdata = record->data;
581         } else {
582                 bdata = hammer_alloc_data(cursor.node->cluster,
583                                           record->rec.base.data_len, &error,
584                                           &cursor.data_buffer);
585                 if (bdata == NULL)
586                         goto done;
587         }
588         rec = hammer_alloc_record(cursor.node->cluster, &error,
589                                   &cursor.record_buffer);
590         if (rec == NULL)
591                 goto fail1;
592
593         /*
594          * Fill everything in and insert our B-Tree node.
595          *
596          * XXX assign rec_id here
597          */
598         *rec = record->rec;
599         if (bdata) {
600                 rec->base.data_crc = crc32(record->data,
601                                            record->rec.base.data_len);
602                 if (record->flags & HAMMER_RECF_EMBEDDED_DATA) {
603                         /*
604                          * Data embedded in record
605                          */
606                         rec->base.data_offset = ((char *)bdata -
607                                                  (char *)&record->rec);
608                         KKASSERT(rec->base.data_offset >= 0 && 
609                                  rec->base.data_offset + rec->base.data_len <=
610                                   sizeof(*rec));
611                         rec->base.data_offset += hammer_bclu_offset(cursor.record_buffer, rec);
612                 } else {
613                         /*
614                          * Data separate from record
615                          */
616                         rec->base.data_offset = hammer_bclu_offset(cursor.data_buffer,bdata);
617                         bcopy(record->data, bdata, rec->base.data_len);
618                         hammer_modify_buffer(cursor.data_buffer);
619                 }
620         }
621         rec->base.rec_id = 0;   /* XXX */
622
623         hammer_modify_buffer(cursor.record_buffer);
624
625         elm.leaf.base = cursor.key_beg;
626         elm.leaf.rec_offset = hammer_bclu_offset(cursor.record_buffer, rec);
627         elm.leaf.data_offset = rec->base.data_offset;
628         elm.leaf.data_len = rec->base.data_len;
629         elm.leaf.data_crc = rec->base.data_crc;
630
631         error = hammer_btree_insert(&cursor, &elm);
632         if (error == 0)
633                 goto done;
634
635         hammer_free_record_ptr(cursor.record_buffer, rec);
636 fail1:
637         if (record->data && (record->flags & HAMMER_RECF_EMBEDDED_DATA) == 0) {
638                 hammer_free_data_ptr(cursor.data_buffer, bdata,
639                                      record->rec.base.data_len);
640         }
641 done:
642         /*
643          * If ENOSPC in cluster fill in the spike structure and return
644          * ENOSPC.
645          */
646         if (error == ENOSPC)
647                 hammer_load_spike(&cursor, spike);
648         hammer_done_cursor(&cursor);
649         return(error);
650 }
651
652 /*
653  * Write out a record using the specified cursor.  The caller does not have
654  * to seek the cursor.  The flags are used to determine whether the data
655  * (if any) is embedded in the record or not.
656  *
657  * The target cursor will be modified by this call.  Note in particular
658  * that HAMMER_CURSOR_INSERT is set.
659  */
660 int
661 hammer_write_record(hammer_cursor_t cursor, hammer_record_ondisk_t orec,
662                     void *data, int cursor_flags)
663 {
664         union hammer_btree_elm elm;
665         hammer_record_ondisk_t nrec;
666         void *bdata;
667         int error;
668
669         cursor->key_beg = orec->base.base;
670         cursor->flags |= HAMMER_CURSOR_INSERT;
671
672         /*
673          * Issue a lookup to position the cursor and locate the cluster.  The
674          * target key should not exist.
675          *
676          * If we run out of space trying to adjust the B-Tree for the
677          * insert, re-lookup without the insert flag so the cursor
678          * is properly positioned for the spike.
679          */
680         error = hammer_btree_lookup(cursor);
681         if (error == 0) {
682                 kprintf("hammer_ip_sync_record: duplicate rec at (%016llx)\n",
683                         orec->base.base.key);
684                 error = EIO;
685         }
686         if (error != ENOENT)
687                 goto done;
688
689         /*
690          * Allocate record and data space now that we know which cluster
691          * the B-Tree node ended up in.
692          */
693         if (data == NULL ||
694             (cursor_flags & HAMMER_RECF_EMBEDDED_DATA)) {
695                 bdata = data;
696         } else {
697                 bdata = hammer_alloc_data(cursor->node->cluster,
698                                           orec->base.data_len, &error,
699                                           &cursor->data_buffer);
700                 if (bdata == NULL)
701                         goto done;
702         }
703         nrec = hammer_alloc_record(cursor->node->cluster, &error,
704                                   &cursor->record_buffer);
705         if (nrec == NULL)
706                 goto fail1;
707
708         /*
709          * Fill everything in and insert our B-Tree node.
710          *
711          * XXX assign rec_id here
712          */
713         *nrec = *orec;
714         nrec->base.data_offset = 0;
715         if (bdata) {
716                 nrec->base.data_crc = crc32(bdata, nrec->base.data_len);
717                 if (cursor_flags & HAMMER_RECF_EMBEDDED_DATA) {
718                         /*
719                          * Data embedded in record
720                          */
721                         nrec->base.data_offset = ((char *)bdata - (char *)orec);
722                         KKASSERT(nrec->base.data_offset >= 0 && 
723                                  nrec->base.data_offset + nrec->base.data_len <
724                                   sizeof(*nrec));
725                         nrec->base.data_offset += hammer_bclu_offset(cursor->record_buffer, nrec);
726                 } else {
727                         /*
728                          * Data separate from record
729                          */
730                         nrec->base.data_offset = hammer_bclu_offset(cursor->data_buffer, bdata);
731                         bcopy(data, bdata, nrec->base.data_len);
732                         hammer_modify_buffer(cursor->data_buffer);
733                 }
734         }
735         nrec->base.rec_id = 0;  /* XXX */
736
737         hammer_modify_buffer(cursor->record_buffer);
738
739         elm.leaf.base = nrec->base.base;
740         elm.leaf.rec_offset = hammer_bclu_offset(cursor->record_buffer, nrec);
741         elm.leaf.data_offset = nrec->base.data_offset;
742         elm.leaf.data_len = nrec->base.data_len;
743         elm.leaf.data_crc = nrec->base.data_crc;
744
745         error = hammer_btree_insert(cursor, &elm);
746         if (error == 0)
747                 goto done;
748
749         hammer_free_record_ptr(cursor->record_buffer, nrec);
750 fail1:
751         if (data && (cursor_flags & HAMMER_RECF_EMBEDDED_DATA) == 0) {
752                 hammer_free_data_ptr(cursor->data_buffer, bdata,
753                                      orec->base.data_len);
754         }
755 done:
756         /* leave cursor intact */
757         return(error);
758 }
759
760 /*
761  * Add the record to the inode's rec_tree.  The low 32 bits of a directory
762  * entry's key is used to deal with hash collisions in the upper 32 bits.
763  * A unique 64 bit key is generated in-memory and may be regenerated a
764  * second time when the directory record is flushed to the on-disk B-Tree.
765  *
766  * A locked and referenced record is passed to this function.  This function
767  * eats the lock and reference.
768  */
769 static
770 int
771 hammer_mem_add(struct hammer_transaction *trans, hammer_record_t record)
772 {
773         while (RB_INSERT(hammer_rec_rb_tree, &record->ip->rec_tree, record)) {
774                 if (record->rec.base.base.rec_type != HAMMER_RECTYPE_DIRENTRY){
775                         hammer_drop_mem_record(record, 1);
776                         return (EEXIST);
777                 }
778                 if (++trans->hmp->namekey_iterator == 0)
779                         ++trans->hmp->namekey_iterator;
780                 record->rec.base.base.key &= ~(0xFFFFFFFFLL);
781                 record->rec.base.base.key |= trans->hmp->namekey_iterator;
782         }
783         record->flags |= HAMMER_RECF_ONRBTREE;
784         hammer_drop_mem_record(record, 0);
785         return(0);
786 }
787
788 /************************************************************************
789  *                   HAMMER INODE MERGED-RECORD FUNCTIONS               *
790  ************************************************************************
791  *
792  * These functions augment the B-Tree scanning functions in hammer_btree.c
793  * by merging in-memory records with on-disk records.
794  */
795
796 /*
797  * Locate a particular record either in-memory or on-disk.
798  *
799  * NOTE: This is basically a standalone routine, hammer_ip_next() may
800  * NOT be called to iterate results.
801  */
802 int
803 hammer_ip_lookup(hammer_cursor_t cursor, struct hammer_inode *ip)
804 {
805         int error;
806
807         /*
808          * If the element is in-memory return it without searching the
809          * on-disk B-Tree
810          */
811         error = hammer_mem_lookup(cursor, ip);
812         if (error == 0) {
813                 cursor->record = &cursor->iprec->rec;
814                 return(error);
815         }
816         if (error != ENOENT)
817                 return(error);
818
819         /*
820          * If the inode has on-disk components search the on-disk B-Tree.
821          */
822         if ((ip->flags & HAMMER_INODE_ONDISK) == 0)
823                 return(error);
824         error = hammer_btree_lookup(cursor);
825         if (error == 0)
826                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
827         return(error);
828 }
829
830 /*
831  * Locate the first record within the cursor's key_beg/key_end range,
832  * restricted to a particular inode.  0 is returned on success, ENOENT
833  * if no records matched the requested range, or some other error.
834  *
835  * When 0 is returned hammer_ip_next() may be used to iterate additional
836  * records within the requested range.
837  */
838 int
839 hammer_ip_first(hammer_cursor_t cursor, struct hammer_inode *ip)
840 {
841         int error;
842
843         /*
844          * Clean up fields and setup for merged scan
845          */
846         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
847         cursor->flags |= HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM;
848         cursor->flags |= HAMMER_CURSOR_DISKEOF | HAMMER_CURSOR_MEMEOF;
849         if (cursor->iprec)
850                 hammer_rel_mem_record(&cursor->iprec);
851
852         /*
853          * Search the on-disk B-Tree.  hammer_btree_lookup() only does an
854          * exact lookup so if we get ENOENT we have to call the iterate
855          * function to validate the first record after the begin key.
856          *
857          * The ATEDISK flag is used by hammer_btree_iterate to determine
858          * whether it must index forwards or not.  It is also used here
859          * to select the next record from in-memory or on-disk.
860          */
861         if (ip->flags & HAMMER_INODE_ONDISK) {
862                 error = hammer_btree_lookup(cursor);
863                 if (error == ENOENT) {
864                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
865                         error = hammer_btree_iterate(cursor);
866                 }
867                 if (error && error != ENOENT) 
868                         return(error);
869                 if (error == 0) {
870                         cursor->flags &= ~HAMMER_CURSOR_DISKEOF;
871                         cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
872                 } else {
873                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
874                 }
875         }
876
877         /*
878          * Search the in-memory record list (Red-Black tree).  Unlike the
879          * B-Tree search, mem_first checks for records in the range.
880          */
881         error = hammer_mem_first(cursor, ip);
882         if (error && error != ENOENT)
883                 return(error);
884         if (error == 0) {
885                 cursor->flags &= ~HAMMER_CURSOR_MEMEOF;
886                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
887         }
888
889         /*
890          * This will return the first matching record.
891          */
892         return(hammer_ip_next(cursor));
893 }
894
895 /*
896  * Retrieve the next record in a merged iteration within the bounds of the
897  * cursor.  This call may be made multiple times after the cursor has been
898  * initially searched with hammer_ip_first().
899  *
900  * 0 is returned on success, ENOENT if no further records match the
901  * requested range, or some other error code is returned.
902  */
903 int
904 hammer_ip_next(hammer_cursor_t cursor)
905 {
906         hammer_btree_elm_t elm;
907         hammer_record_t rec;
908         int error;
909         int r;
910
911         /*
912          * Load the current on-disk and in-memory record.  If we ate any
913          * records we have to get the next one. 
914          *
915          * If we deleted the last on-disk record we had scanned ATEDISK will
916          * be clear and DELBTREE will be set, forcing a call to iterate. The
917          * fact that ATEDISK is clear causes iterate to re-test the 'current'
918          * element.  If ATEDISK is set, iterate will skip the 'current'
919          * element.
920          *
921          * Get the next on-disk record
922          */
923         if (cursor->flags & (HAMMER_CURSOR_ATEDISK|HAMMER_CURSOR_DELBTREE)) {
924                 if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
925                         error = hammer_btree_iterate(cursor);
926                         if (error == 0)
927                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
928                         else
929                                 cursor->flags |= HAMMER_CURSOR_DISKEOF |
930                                                  HAMMER_CURSOR_ATEDISK;
931                 }
932         }
933
934         /*
935          * Get the next in-memory record.  The record can be ripped out
936          * of the RB tree so we maintain a scan_info structure to track
937          * the next node.
938          *
939          * hammer_rec_scan_cmp:  Is the record still in our general range,
940          *                       (non-inclusive of snapshot exclusions)?
941          * hammer_rec_scan_callback: Is the record in our snapshot?
942          */
943         if (cursor->flags & HAMMER_CURSOR_ATEMEM) {
944                 if ((cursor->flags & HAMMER_CURSOR_MEMEOF) == 0) {
945                         hammer_rel_mem_record(&cursor->iprec);
946                         rec = cursor->scan.node;        /* next node */
947                         while (rec) {
948                                 if (hammer_rec_scan_cmp(rec, cursor) != 0)
949                                         break;
950                                 if (hammer_rec_scan_callback(rec, cursor) != 0)
951                                         break;
952                                 rec = hammer_rec_rb_tree_RB_NEXT(rec);
953                         }
954                         if (cursor->iprec) {
955                                 cursor->flags &= ~HAMMER_CURSOR_ATEMEM;
956                                 hammer_ref(&cursor->iprec->lock);
957                                 cursor->scan.node =
958                                         hammer_rec_rb_tree_RB_NEXT(rec);
959                         } else {
960                                 cursor->flags |= HAMMER_CURSOR_MEMEOF;
961                         }
962                 }
963         }
964
965         /*
966          * Extract either the disk or memory record depending on their
967          * relative position.
968          */
969         error = 0;
970         switch(cursor->flags & (HAMMER_CURSOR_ATEDISK | HAMMER_CURSOR_ATEMEM)) {
971         case 0:
972                 /*
973                  * Both entries valid
974                  */
975                 elm = &cursor->node->ondisk->elms[cursor->index];
976                 r = hammer_btree_cmp(&elm->base, &cursor->iprec->rec.base.base);
977                 if (r < 0) {
978                         error = hammer_btree_extract(cursor,
979                                                      HAMMER_CURSOR_GET_RECORD);
980                         cursor->flags |= HAMMER_CURSOR_ATEDISK;
981                         break;
982                 }
983                 /* fall through to the memory entry */
984         case HAMMER_CURSOR_ATEDISK:
985                 /*
986                  * Only the memory entry is valid
987                  */
988                 cursor->record = &cursor->iprec->rec;
989                 cursor->flags |= HAMMER_CURSOR_ATEMEM;
990                 break;
991         case HAMMER_CURSOR_ATEMEM:
992                 /*
993                  * Only the disk entry is valid
994                  */
995                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
996                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
997                 break;
998         default:
999                 /*
1000                  * Neither entry is valid
1001                  *
1002                  * XXX error not set properly
1003                  */
1004                 cursor->record = NULL;
1005                 error = ENOENT;
1006                 break;
1007         }
1008         return(error);
1009 }
1010
1011 /*
1012  * Resolve the cursor->data pointer for the current cursor position in
1013  * a merged iteration.
1014  */
1015 int
1016 hammer_ip_resolve_data(hammer_cursor_t cursor)
1017 {
1018         int error;
1019
1020         if (cursor->iprec && cursor->record == &cursor->iprec->rec) {
1021                 cursor->data = cursor->iprec->data;
1022                 error = 0;
1023         } else {
1024                 error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_DATA);
1025         }
1026         return(error);
1027 }
1028
1029 /*
1030  * Delete all records within the specified range for inode ip.
1031  *
1032  * NOTE: An unaligned range will cause new records to be added to cover
1033  * the edge cases. (XXX not implemented yet).
1034  *
1035  * NOTE: ran_end is inclusive (e.g. 0,1023 instead of 0,1024).
1036  *
1037  * NOTE: Record keys for regular file data have to be special-cased since
1038  * they indicate the end of the range (key = base + bytes).
1039  *
1040  * NOTE: The spike structure must be filled in if we return ENOSPC.
1041  */
1042 int
1043 hammer_ip_delete_range(hammer_transaction_t trans, hammer_inode_t ip,
1044                        int64_t ran_beg, int64_t ran_end,
1045                        struct hammer_cursor **spike)
1046 {
1047         struct hammer_cursor cursor;
1048         hammer_record_ondisk_t rec;
1049         hammer_base_elm_t base;
1050         int error;
1051         int64_t off;
1052
1053         hammer_init_cursor_ip(&cursor, ip);
1054
1055         cursor.key_beg.obj_id = ip->obj_id;
1056         cursor.key_beg.create_tid = ip->obj_asof;
1057         cursor.key_beg.delete_tid = 0;
1058         cursor.key_beg.obj_type = 0;
1059
1060         cursor.key_end = cursor.key_beg;
1061         if (ip->ino_rec.base.base.obj_type == HAMMER_OBJTYPE_DBFILE) {
1062                 cursor.key_beg.key = ran_beg;
1063                 cursor.key_beg.rec_type = HAMMER_RECTYPE_DB;
1064                 cursor.key_end.rec_type = HAMMER_RECTYPE_DB;
1065                 cursor.key_end.key = ran_end;
1066         } else {
1067                 /*
1068                  * The key in the B-Tree is (base+bytes), so the first possible
1069                  * matching key is ran_beg + 1.
1070                  */
1071                 int64_t tmp64;
1072
1073                 cursor.key_beg.key = ran_beg + 1;
1074                 cursor.key_beg.rec_type = HAMMER_RECTYPE_DATA;
1075                 cursor.key_end.rec_type = HAMMER_RECTYPE_DATA;
1076
1077                 tmp64 = ran_end + MAXPHYS + 1;  /* work around GCC-4 bug */
1078                 if (tmp64 < ran_end)
1079                         cursor.key_end.key = 0x7FFFFFFFFFFFFFFFLL;
1080                 else
1081                         cursor.key_end.key = ran_end + MAXPHYS + 1;
1082         }
1083         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
1084
1085         error = hammer_ip_first(&cursor, ip);
1086
1087         /*
1088          * Iterate through matching records and mark them as deleted.
1089          */
1090         while (error == 0) {
1091                 rec = cursor.record;
1092                 base = &rec->base.base;
1093
1094                 KKASSERT(base->delete_tid == 0);
1095
1096                 /*
1097                  * There may be overlap cases for regular file data.  Also
1098                  * remember the key for a regular file record is the offset
1099                  * of the last byte of the record (base + len - 1), NOT the
1100                  * base offset.
1101                  */
1102 #if 0
1103                 kprintf("delete_range rec_type %02x\n", base->rec_type);
1104 #endif
1105                 if (base->rec_type == HAMMER_RECTYPE_DATA) {
1106 #if 0
1107                         kprintf("delete_range loop key %016llx\n",
1108                                 base->key - rec->base.data_len);
1109 #endif
1110                         off = base->key - rec->base.data_len;
1111                         /*
1112                          * Check the left edge case.  We currently do not
1113                          * split existing records.
1114                          */
1115                         if (off < ran_beg) {
1116                                 panic("hammer left edge case %016llx %d\n",
1117                                         base->key, rec->base.data_len);
1118                         }
1119
1120                         /*
1121                          * Check the right edge case.  Note that the
1122                          * record can be completely out of bounds, which
1123                          * terminates the search.
1124                          *
1125                          * base->key is exclusive of the right edge while
1126                          * ran_end is inclusive of the right edge.  The
1127                          * (key - data_len) left boundary is inclusive.
1128                          *
1129                          * XXX theory-check this test at some point, are
1130                          * we missing a + 1 somewhere?  Note that ran_end
1131                          * could overflow.
1132                          */
1133                         if (base->key > ran_end) {
1134                                 if (base->key - rec->base.data_len > ran_end) {
1135                                         kprintf("right edge OOB\n");
1136                                         break;
1137                                 }
1138                                 panic("hammer right edge case\n");
1139                         }
1140                 }
1141
1142                 /*
1143                  * Mark the record and B-Tree entry as deleted.  This will
1144                  * also physically delete the B-Tree entry, record, and
1145                  * data if the retention policy dictates.  The function
1146                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1147                  * uses to perform a fixup.
1148                  */
1149                 error = hammer_ip_delete_record(&cursor, trans->tid);
1150                 if (error)
1151                         break;
1152                 error = hammer_ip_next(&cursor);
1153         }
1154         hammer_done_cursor(&cursor);
1155         if (error == ENOENT)
1156                 error = 0;
1157         return(error);
1158 }
1159
1160 int
1161 hammer_ip_delete_range_all(hammer_transaction_t trans, hammer_inode_t ip)
1162 {
1163         struct hammer_cursor cursor;
1164         hammer_record_ondisk_t rec;
1165         hammer_base_elm_t base;
1166         int error;
1167
1168         hammer_init_cursor_ip(&cursor, ip);
1169
1170         cursor.key_beg.obj_id = ip->obj_id;
1171         cursor.key_beg.create_tid = ip->obj_asof;
1172         cursor.key_beg.delete_tid = 0;
1173         cursor.key_beg.obj_type = 0;
1174         cursor.key_beg.rec_type = 0;
1175         cursor.key_beg.key = HAMMER_MIN_KEY;
1176
1177         cursor.key_end = cursor.key_beg;
1178         cursor.key_end.rec_type = 0xFFFF;
1179         cursor.key_end.key = HAMMER_MAX_KEY;
1180
1181         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
1182
1183         error = hammer_ip_first(&cursor, ip);
1184
1185         /*
1186          * Iterate through matching records and mark them as deleted.
1187          */
1188         while (error == 0) {
1189                 rec = cursor.record;
1190                 base = &rec->base.base;
1191
1192                 KKASSERT(base->delete_tid == 0);
1193
1194                 /*
1195                  * Mark the record and B-Tree entry as deleted.  This will
1196                  * also physically delete the B-Tree entry, record, and
1197                  * data if the retention policy dictates.  The function
1198                  * will set HAMMER_CURSOR_DELBTREE which hammer_ip_next()
1199                  * uses to perform a fixup.
1200                  */
1201                 error = hammer_ip_delete_record(&cursor, trans->tid);
1202                 if (error)
1203                         break;
1204                 error = hammer_ip_next(&cursor);
1205         }
1206         hammer_done_cursor(&cursor);
1207         if (error == ENOENT)
1208                 error = 0;
1209         return(error);
1210 }
1211
1212 /*
1213  * Delete the record at the current cursor
1214  */
1215 int
1216 hammer_ip_delete_record(hammer_cursor_t cursor, hammer_tid_t tid)
1217 {
1218         hammer_btree_elm_t elm;
1219         hammer_mount_t hmp;
1220         int error;
1221
1222         /*
1223          * In-memory (unsynchronized) records can simply be freed.
1224          */
1225         cursor->flags &= ~HAMMER_CURSOR_DELBTREE;
1226         if (cursor->record == &cursor->iprec->rec) {
1227                 hammer_free_mem_record(cursor->iprec); /* XXX */
1228                 return(0);
1229         }
1230
1231         /*
1232          * On-disk records are marked as deleted by updating their delete_tid.
1233          */
1234         error = hammer_btree_extract(cursor, HAMMER_CURSOR_GET_RECORD);
1235         elm = NULL;
1236         hmp = cursor->node->cluster->volume->hmp;
1237
1238         if (error == 0) {
1239                 elm = &cursor->node->ondisk->elms[cursor->index];
1240                 cursor->record->base.base.delete_tid = tid;
1241                 elm->leaf.base.delete_tid = tid;
1242                 hammer_modify_buffer(cursor->record_buffer);
1243                 hammer_modify_node(cursor->node);
1244         }
1245
1246         /*
1247          * If we were mounted with the nohistory option, we physically
1248          * delete the record.
1249          */
1250         if (error == 0 && (hmp->hflags & HMNT_NOHISTORY)) {
1251                 int32_t rec_offset;
1252                 int32_t data_offset;
1253                 int32_t data_len;
1254                 hammer_cluster_t cluster;
1255
1256                 rec_offset = elm->leaf.rec_offset;
1257                 data_offset = elm->leaf.data_offset;
1258                 data_len = elm->leaf.data_len;
1259 #if 0
1260                 kprintf("hammer_ip_delete_record: %08x %08x/%d\n",
1261                         rec_offset, data_offset, data_len);
1262 #endif
1263                 cluster = cursor->node->cluster;
1264                 hammer_ref_cluster(cluster);
1265
1266                 error = hammer_btree_delete(cursor);
1267                 if (error == 0) {
1268                         /*
1269                          * This forces a fixup for the iteration because
1270                          * the cursor is now either sitting at the 'next'
1271                          * element or sitting at the end of a leaf.
1272                          */
1273                         if ((cursor->flags & HAMMER_CURSOR_DISKEOF) == 0) {
1274                                 cursor->flags |= HAMMER_CURSOR_DELBTREE;
1275                                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
1276                         }
1277                         hammer_free_record(cluster, rec_offset);
1278                         if (data_offset && (data_offset - rec_offset < 0 ||
1279                             data_offset - rec_offset >= HAMMER_RECORD_SIZE)) {
1280                                 hammer_free_data(cluster, data_offset,data_len);
1281                         }
1282                 }
1283                 hammer_rel_cluster(cluster, 0);
1284                 if (error) {
1285                         kprintf("hammer_ip_delete_record: unable to physically delete the record!\n");
1286                         error = 0;
1287                 }
1288         }
1289         return(error);
1290 }
1291