1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=8:tabstop=8:
4 * Copyright (c) 2002, 2003 Cluster File Systems, Inc.
6 * This file is part of Lustre, http://www.lustre.org.
8 * Lustre is free software; you can redistribute it and/or
9 * modify it under the terms of version 2 of the GNU General Public
10 * License as published by the Free Software Foundation.
12 * Lustre is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Lustre; if not, write to the Free Software
19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 * Copyright (C) 2002, 2003 Cluster File Systems, Inc
23 * our offset trees (otrees) track single-bit state of offsets in an
28 #include <linux/version.h>
29 #include <linux/config.h>
30 #include <linux/module.h>
32 #define DEBUG_SUBSYSTEM S_OSC
33 #include <linux/kp30.h>
34 #include <linux/obd.h>
35 #include <linux/lustre_debug.h>
36 #include <linux/lustre_otree.h>
38 struct offset_extent {
40 unsigned long oe_start, oe_end;
43 static struct offset_extent * ot_find_oe(rb_root_t *root,
44 struct offset_extent *needle)
46 struct rb_node_s *node = root->rb_node;
47 struct offset_extent *oe;
50 CDEBUG(D_INODE, "searching [%lu -> %lu]\n", needle->oe_start,
54 oe = rb_entry(node, struct offset_extent, oe_node);
55 if (needle->oe_end < oe->oe_start)
57 else if (needle->oe_start > oe->oe_end)
58 node = node->rb_right;
60 CDEBUG(D_INODE, "returning [%lu -> %lu]\n",
61 oe->oe_start, oe->oe_end);
68 /* do the rbtree mechanics to insert a node, callers are responsible
69 * for making sure that this new node doesn't overlap with existing
71 static void ot_indert_oe(rb_root_t *root, struct offset_extent *new_oe)
73 rb_node_t ** p = &root->rb_node;
74 rb_node_t * parent = NULL;
75 struct offset_extent *oe;
78 LASSERT(new_oe->oe_start <= new_oe->oe_end);
82 oe = rb_entry(parent, struct offset_extent, oe_node);
83 if ( new_oe->oe_end < oe->oe_start )
85 else if ( new_oe->oe_start > oe->oe_end )
90 rb_link_node(&new_oe->oe_node, parent, p);
91 rb_insert_color(&new_oe->oe_node, root);
95 int ot_mark_offset(struct otree *ot, unsigned long offset)
97 struct offset_extent needle, *oe, *new_oe;
101 OBD_ALLOC(new_oe, sizeof(*new_oe));
105 spin_lock(&ot->ot_lock);
107 /* find neighbours that we might glom on to */
108 needle.oe_start = (offset > 0) ? offset - 1 : offset;
109 needle.oe_end = (offset < ~0) ? offset + 1 : offset;
110 oe = ot_find_oe(&ot->ot_root, &needle);
112 new_oe->oe_start = offset;
113 new_oe->oe_end = offset;
114 ot_indert_oe(&ot->ot_root, new_oe);
120 /* already recorded */
121 if ( offset >= oe->oe_start && offset <= oe->oe_end )
124 /* ok, need to check for adjacent neighbours */
125 needle.oe_start = offset;
126 needle.oe_end = offset;
127 if (ot_find_oe(&ot->ot_root, &needle))
130 /* ok, its safe to extend the oe we found */
131 if ( offset == oe->oe_start - 1 )
133 else if ( offset == oe->oe_end + 1 )
140 CDEBUG(D_INODE, "%lu now dirty\n", ot->ot_num_marked);
141 spin_unlock(&ot->ot_lock);
143 OBD_FREE(new_oe, sizeof(*new_oe));
147 int ot_clear_extent(struct otree *ot, unsigned long start, unsigned long end)
149 struct offset_extent needle, *oe, *new_oe;
153 /* will allocate more intelligently later */
154 OBD_ALLOC(new_oe, sizeof(*new_oe));
158 needle.oe_start = start;
161 spin_lock(&ot->ot_lock);
162 for ( ; (oe = ot_find_oe(&ot->ot_root, &needle)) ; ) {
165 /* see if we're punching a hole and need to create a node */
166 if (oe->oe_start < start && oe->oe_end > end) {
167 new_oe->oe_start = end + 1;
168 new_oe->oe_end = oe->oe_end;
169 oe->oe_end = start - 1;
170 ot_indert_oe(&ot->ot_root, new_oe);
172 ot->ot_num_marked -= end - start + 1;
176 /* overlapping edges */
177 if (oe->oe_start < start && oe->oe_end <= end) {
178 ot->ot_num_marked -= oe->oe_end - start + 1;
179 oe->oe_end = start - 1;
183 if (oe->oe_end > end && oe->oe_start >= start) {
184 ot->ot_num_marked -= end - oe->oe_start + 1;
185 oe->oe_start = end + 1;
190 /* an extent entirely within the one we're clearing */
191 rb_erase(&oe->oe_node, &ot->ot_root);
192 ot->ot_num_marked -= oe->oe_end - oe->oe_start + 1;
193 spin_unlock(&ot->ot_lock);
194 OBD_FREE(oe, sizeof(*oe));
195 spin_lock(&ot->ot_lock);
197 CDEBUG(D_INODE, "%lu now dirty\n", ot->ot_num_marked);
198 spin_unlock(&ot->ot_lock);
200 OBD_FREE(new_oe, sizeof(*new_oe));
204 int ot_find_marked_extent(struct otree *ot, unsigned long *start,
207 struct offset_extent needle, *oe;
211 needle.oe_start = *start;
212 needle.oe_end = *end;
214 spin_lock(&ot->ot_lock);
215 oe = ot_find_oe(&ot->ot_root, &needle);
217 *start = oe->oe_start;
221 spin_unlock(&ot->ot_lock);
226 int ot_last_marked(struct otree *ot, unsigned long *last)
228 struct rb_node_s *found, *node;
229 struct offset_extent *oe;
233 spin_lock(&ot->ot_lock);
234 for (node = ot->ot_root.rb_node, found = NULL;
236 found = node, node = node->rb_right)
240 oe = rb_entry(found, struct offset_extent, oe_node);
244 spin_unlock(&ot->ot_lock);
248 unsigned long ot_num_marked(struct otree *ot)
250 return ot->ot_num_marked;
253 void ot_init(struct otree *ot)
255 CDEBUG(D_INODE, "initializing %p\n", ot);
256 spin_lock_init(&ot->ot_lock);
257 ot->ot_num_marked = 0;
258 ot->ot_root.rb_node = NULL;
261 EXPORT_SYMBOL(ot_mark_offset);
262 EXPORT_SYMBOL(ot_clear_extent);
263 EXPORT_SYMBOL(ot_find_marked_extent);
264 EXPORT_SYMBOL(ot_last_marked);
265 EXPORT_SYMBOL(ot_num_marked);
266 EXPORT_SYMBOL(ot_init);