lustre/obdclass/otree.c

   1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
   2  * vim:expandtab:shiftwidth=8:tabstop=8:
   3  *
   4  *  Copyright (c) 2002, 2003 Cluster File Systems, Inc.
   5  *
   6  *   This file is part of Lustre, http://www.lustre.org.
   7  *
   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.
  11  *
  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.
  16  *
  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.
  20  *
  21  *  Copyright (C) 2002, 2003  Cluster File Systems, Inc
  22  *
  23  *  our offset trees (otrees) track single-bit state of offsets in an
  24  *  extent tree.
  25  */
  26
  27 #define EXPORT_SYMTAB
  28 #include <linux/version.h>
  29 #include <linux/config.h>
  30 #include <linux/module.h>
  31
  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>
  37
  38 struct offset_extent {
  39         rb_node_t       oe_node;
  40         unsigned long   oe_start, oe_end;
  41 };
  42
  43 static struct offset_extent * ot_find_oe(rb_root_t *root,
  44                                          struct offset_extent *needle)
  45 {
  46         struct rb_node_s *node = root->rb_node;
  47         struct offset_extent *oe;
  48         ENTRY;
  49
  50         CDEBUG(D_INODE, "searching [%lu -> %lu]\n", needle->oe_start,
  51                needle->oe_end);
  52
  53         while (node) {
  54                 oe = rb_entry(node, struct offset_extent, oe_node);
  55                 if (needle->oe_end < oe->oe_start)
  56                         node = node->rb_left;
  57                 else if (needle->oe_start > oe->oe_end)
  58                         node = node->rb_right;
  59                 else {
  60                         CDEBUG(D_INODE, "returning [%lu -> %lu]\n",
  61                                oe->oe_start, oe->oe_end);
  62                         RETURN(oe);
  63                 }
  64         }
  65         RETURN(NULL);
  66 }
  67
  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
  70  * nodes */
  71 static void ot_indert_oe(rb_root_t *root, struct offset_extent *new_oe)
  72 {
  73         rb_node_t ** p = &root->rb_node;
  74         rb_node_t * parent = NULL;
  75         struct offset_extent *oe;
  76         ENTRY;
  77
  78         LASSERT(new_oe->oe_start <= new_oe->oe_end);
  79
  80         while (*p) {
  81                 parent = *p;
  82                 oe = rb_entry(parent, struct offset_extent, oe_node);
  83                 if ( new_oe->oe_end < oe->oe_start )
  84                         p = &(*p)->rb_left;
  85                 else if ( new_oe->oe_start > oe->oe_end )
  86                         p = &(*p)->rb_right;
  87                 else
  88                         LBUG();
  89         }
  90         rb_link_node(&new_oe->oe_node, parent, p);
  91         rb_insert_color(&new_oe->oe_node, root);
  92         EXIT;
  93 }
  94
  95 int ot_mark_offset(struct otree *ot, unsigned long offset)
  96 {
  97         struct offset_extent needle, *oe, *new_oe;
  98         int rc = 0;
  99         ENTRY;
 100
 101         OBD_ALLOC(new_oe, sizeof(*new_oe));
 102         if (new_oe == NULL)
 103                 RETURN(-ENOMEM);
 104
 105         spin_lock(&ot->ot_lock);
 106
 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);
 111         if ( oe == NULL ) {
 112                 new_oe->oe_start = offset;
 113                 new_oe->oe_end = offset;
 114                 ot_indert_oe(&ot->ot_root, new_oe);
 115                 ot->ot_num_marked++;
 116                 new_oe = NULL;
 117                 GOTO(out, rc);
 118         }
 119
 120         /* already recorded */
 121         if ( offset >= oe->oe_start && offset <= oe->oe_end )
 122                 GOTO(out, rc);
 123
 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))
 128                 GOTO(out, rc);
 129
 130         /* ok, its safe to extend the oe we found */
 131         if ( offset == oe->oe_start - 1 )
 132                 oe->oe_start--;
 133         else if ( offset == oe->oe_end + 1 )
 134                 oe->oe_end++;
 135         else
 136                 LBUG();
 137         ot->ot_num_marked++;
 138
 139 out:
 140         CDEBUG(D_INODE, "%lu now dirty\n", ot->ot_num_marked);
 141         spin_unlock(&ot->ot_lock);
 142         if (new_oe)
 143                 OBD_FREE(new_oe, sizeof(*new_oe));
 144         RETURN(rc);
 145 }
 146
 147 int ot_clear_extent(struct otree *ot, unsigned long start, unsigned long end)
 148 {
 149         struct offset_extent needle, *oe, *new_oe;
 150         int rc = 0;
 151         ENTRY;
 152
 153         /* will allocate more intelligently later */
 154         OBD_ALLOC(new_oe, sizeof(*new_oe));
 155         if (new_oe == NULL)
 156                 RETURN(-ENOMEM);
 157
 158         needle.oe_start = start;
 159         needle.oe_end = end;
 160
 161         spin_lock(&ot->ot_lock);
 162         for ( ; (oe = ot_find_oe(&ot->ot_root, &needle)) ; ) {
 163                 rc = 0;
 164
 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);
 171                         new_oe = NULL;
 172                         ot->ot_num_marked -= end - start + 1;
 173                         break;
 174                 }
 175
 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;
 180                         oe = NULL;
 181                         continue;
 182                 }
 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;
 186                         oe = NULL;
 187                         continue;
 188                 }
 189
 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);
 196         }
 197         CDEBUG(D_INODE, "%lu now dirty\n", ot->ot_num_marked);
 198         spin_unlock(&ot->ot_lock);
 199         if (new_oe)
 200                 OBD_FREE(new_oe, sizeof(*new_oe));
 201         RETURN(rc);
 202 }
 203
 204 int ot_find_marked_extent(struct otree *ot, unsigned long *start,
 205                   unsigned long *end)
 206 {
 207         struct offset_extent needle, *oe;
 208         int rc = -ENOENT;
 209         ENTRY;
 210
 211         needle.oe_start = *start;
 212         needle.oe_end = *end;
 213
 214         spin_lock(&ot->ot_lock);
 215         oe = ot_find_oe(&ot->ot_root, &needle);
 216         if (oe) {
 217                 *start = oe->oe_start;
 218                 *end = oe->oe_end;
 219                 rc = 0;
 220         }
 221         spin_unlock(&ot->ot_lock);
 222
 223         RETURN(rc);
 224 }
 225
 226 int ot_last_marked(struct otree *ot, unsigned long *last)
 227 {
 228         struct rb_node_s *found, *node;
 229         struct offset_extent *oe;
 230         int rc = -ENOENT;
 231         ENTRY;
 232
 233         spin_lock(&ot->ot_lock);
 234         for (node = ot->ot_root.rb_node, found = NULL;
 235              node;
 236              found = node, node = node->rb_right)
 237                 ;
 238
 239         if (found) {
 240                 oe = rb_entry(found, struct offset_extent, oe_node);
 241                 *last = oe->oe_end;
 242                 rc = 0;
 243         }
 244         spin_unlock(&ot->ot_lock);
 245         RETURN(rc);
 246 }
 247
 248 unsigned long ot_num_marked(struct otree *ot)
 249 {
 250         return ot->ot_num_marked;
 251 }
 252
 253 void ot_init(struct otree *ot)
 254 {
 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;
 259 }
 260
 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);