lustre/fld/fld_cache.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 only,
   8  * as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License version 2 for more details (a copy is included
  14  * in the LICENSE file that accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * version 2 along with this program; If not, see
  18  * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
  19  *
  20  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  21  * CA 95054 USA or visit www.sun.com if you need additional information or
  22  * have any questions.
  23  *
  24  * GPL HEADER END
  25  */
  26 /*
  27  * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
  28  * Use is subject to license terms.
  29  */
  30 /*
  31  * This file is part of Lustre, http://www.lustre.org/
  32  * Lustre is a trademark of Sun Microsystems, Inc.
  33  *
  34  * lustre/fld/fld_cache.c
  35  *
  36  * FLD (Fids Location Database)
  37  *
  38  * Author: Pravin Shelar <pravin.shelar@sun.com>
  39  * Author: Yury Umanets <umka@clusterfs.com>
  40  */
  41
  42 #define DEBUG_SUBSYSTEM S_FLD
  43
  44 #ifdef __KERNEL__
  45 # include <libcfs/libcfs.h>
  46 # include <linux/module.h>
  47 # include <linux/jbd.h>
  48 # include <asm/div64.h>
  49 #else /* __KERNEL__ */
  50 # include <liblustre.h>
  51 # include <libcfs/list.h>
  52 #endif
  53
  54 #include <obd.h>
  55 #include <obd_class.h>
  56 #include <lustre_ver.h>
  57 #include <obd_support.h>
  58 #include <lprocfs_status.h>
  59
  60 #include <dt_object.h>
  61 #include <md_object.h>
  62 #include <lustre_req_layout.h>
  63 #include <lustre_fld.h>
  64 #include "fld_internal.h"
  65
  66 /**
  67  * create fld cache.
  68  */
  69 struct fld_cache *fld_cache_init(const char *name,
  70                                  int cache_size, int cache_threshold)
  71 {
  72         struct fld_cache *cache;
  73         ENTRY;
  74
  75         LASSERT(name != NULL);
  76         LASSERT(cache_threshold < cache_size);
  77
  78         OBD_ALLOC_PTR(cache);
  79         if (cache == NULL)
  80                 RETURN(ERR_PTR(-ENOMEM));
  81
  82         CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
  83         CFS_INIT_LIST_HEAD(&cache->fci_lru);
  84
  85         cache->fci_cache_count = 0;
  86         cfs_spin_lock_init(&cache->fci_lock);
  87
  88         strncpy(cache->fci_name, name,
  89                 sizeof(cache->fci_name));
  90
  91         cache->fci_cache_size = cache_size;
  92         cache->fci_threshold = cache_threshold;
  93
  94         /* Init fld cache info. */
  95         memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
  96
  97         CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
  98                cache->fci_name, cache_size, cache_threshold);
  99
 100         RETURN(cache);
 101 }
 102
 103 /**
 104  * destroy fld cache.
 105  */
 106 void fld_cache_fini(struct fld_cache *cache)
 107 {
 108         __u64 pct;
 109         ENTRY;
 110
 111         LASSERT(cache != NULL);
 112         fld_cache_flush(cache);
 113
 114         if (cache->fci_stat.fst_count > 0) {
 115                 pct = cache->fci_stat.fst_cache * 100;
 116                 do_div(pct, cache->fci_stat.fst_count);
 117         } else {
 118                 pct = 0;
 119         }
 120
 121         CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
 122         CDEBUG(D_INFO, "  Total reqs: "LPU64"\n", cache->fci_stat.fst_count);
 123         CDEBUG(D_INFO, "  Cache reqs: "LPU64"\n", cache->fci_stat.fst_cache);
 124         CDEBUG(D_INFO, "  Cache hits: "LPU64"%%\n", pct);
 125
 126         OBD_FREE_PTR(cache);
 127
 128         EXIT;
 129 }
 130
 131 /**
 132  * delete given node from list.
 133  */
 134 static inline void fld_cache_entry_delete(struct fld_cache *cache,
 135                                           struct fld_cache_entry *node)
 136 {
 137         cfs_list_del(&node->fce_list);
 138         cfs_list_del(&node->fce_lru);
 139         cache->fci_cache_count--;
 140         OBD_FREE_PTR(node);
 141 }
 142
 143 /**
 144  * fix list by checking new entry with NEXT entry in order.
 145  */
 146 static void fld_fix_new_list(struct fld_cache *cache)
 147 {
 148         struct fld_cache_entry *f_curr;
 149         struct fld_cache_entry *f_next;
 150         struct lu_seq_range *c_range;
 151         struct lu_seq_range *n_range;
 152         cfs_list_t *head = &cache->fci_entries_head;
 153         ENTRY;
 154
 155 restart_fixup:
 156
 157         cfs_list_for_each_entry_safe(f_curr, f_next, head, fce_list) {
 158                 c_range = &f_curr->fce_range;
 159                 n_range = &f_next->fce_range;
 160
 161                 LASSERT(range_is_sane(c_range));
 162                 if (&f_next->fce_list == head)
 163                         break;
 164
 165                 if (c_range->lsr_flags != n_range->lsr_flags)
 166                         continue;
 167
 168                 LASSERTF(c_range->lsr_start <= n_range->lsr_start,
 169                          "cur lsr_start "DRANGE" next lsr_start "DRANGE"\n",
 170                          PRANGE(c_range), PRANGE(n_range));
 171
 172                 /* check merge possibility with next range */
 173                 if (c_range->lsr_end == n_range->lsr_start) {
 174                         if (c_range->lsr_index != n_range->lsr_index)
 175                                 continue;
 176                         n_range->lsr_start = c_range->lsr_start;
 177                         fld_cache_entry_delete(cache, f_curr);
 178                         continue;
 179                 }
 180
 181                 /* check if current range overlaps with next range. */
 182                 if (n_range->lsr_start < c_range->lsr_end) {
 183                         if (c_range->lsr_index == n_range->lsr_index) {
 184                                 n_range->lsr_start = c_range->lsr_start;
 185                                 n_range->lsr_end = max(c_range->lsr_end,
 186                                                        n_range->lsr_end);
 187                                 fld_cache_entry_delete(cache, f_curr);
 188                         } else {
 189                                 if (n_range->lsr_end <= c_range->lsr_end) {
 190                                         *n_range = *c_range;
 191                                         fld_cache_entry_delete(cache, f_curr);
 192                                 } else
 193                                         n_range->lsr_start = c_range->lsr_end;
 194                         }
 195
 196                         /* we could have overlap over next
 197                          * range too. better restart. */
 198                         goto restart_fixup;
 199                 }
 200
 201                 /* kill duplicates */
 202                 if (c_range->lsr_start == n_range->lsr_start &&
 203                     c_range->lsr_end == n_range->lsr_end)
 204                         fld_cache_entry_delete(cache, f_curr);
 205         }
 206
 207         EXIT;
 208 }
 209
 210 /**
 211  * add node to fld cache
 212  */
 213 static inline void fld_cache_entry_add(struct fld_cache *cache,
 214                                        struct fld_cache_entry *f_new,
 215                                        cfs_list_t *pos)
 216 {
 217         cfs_list_add(&f_new->fce_list, pos);
 218         cfs_list_add(&f_new->fce_lru, &cache->fci_lru);
 219
 220         cache->fci_cache_count++;
 221         fld_fix_new_list(cache);
 222 }
 223
 224 /**
 225  * Check if cache needs to be shrunk. If so - do it.
 226  * Remove one entry in list and so on until cache is shrunk enough.
 227  */
 228 static int fld_cache_shrink(struct fld_cache *cache)
 229 {
 230         struct fld_cache_entry *flde;
 231         cfs_list_t *curr;
 232         int num = 0;
 233         ENTRY;
 234
 235         LASSERT(cache != NULL);
 236
 237         if (cache->fci_cache_count < cache->fci_cache_size)
 238                 RETURN(0);
 239
 240         curr = cache->fci_lru.prev;
 241
 242         while (cache->fci_cache_count + cache->fci_threshold >
 243                cache->fci_cache_size && curr != &cache->fci_lru) {
 244
 245                 flde = cfs_list_entry(curr, struct fld_cache_entry, fce_lru);
 246                 curr = curr->prev;
 247                 fld_cache_entry_delete(cache, flde);
 248                 num++;
 249         }
 250
 251         CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
 252                "%d entries\n", cache->fci_name, num);
 253
 254         RETURN(0);
 255 }
 256
 257 /**
 258  * kill all fld cache entries.
 259  */
 260 void fld_cache_flush(struct fld_cache *cache)
 261 {
 262         ENTRY;
 263
 264         cfs_spin_lock(&cache->fci_lock);
 265         cache->fci_cache_size = 0;
 266         fld_cache_shrink(cache);
 267         cfs_spin_unlock(&cache->fci_lock);
 268
 269         EXIT;
 270 }
 271
 272 /**
 273  * punch hole in existing range. divide this range and add new
 274  * entry accordingly.
 275  */
 276
 277 void fld_cache_punch_hole(struct fld_cache *cache,
 278                           struct fld_cache_entry *f_curr,
 279                           struct fld_cache_entry *f_new)
 280 {
 281         const struct lu_seq_range *range = &f_new->fce_range;
 282         const seqno_t new_start  = range->lsr_start;
 283         const seqno_t new_end  = range->lsr_end;
 284         struct fld_cache_entry *fldt;
 285
 286         ENTRY;
 287         OBD_ALLOC_GFP(fldt, sizeof *fldt, CFS_ALLOC_ATOMIC);
 288         if (!fldt) {
 289                 OBD_FREE_PTR(f_new);
 290                 EXIT;
 291                 /* overlap is not allowed, so dont mess up list. */
 292                 return;
 293         }
 294         /*  break f_curr RANGE into three RANGES:
 295          *        f_curr, f_new , fldt
 296          */
 297
 298         /* f_new = *range */
 299
 300         /* fldt */
 301         fldt->fce_range.lsr_start = new_end;
 302         fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
 303         fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
 304
 305         /* f_curr */
 306         f_curr->fce_range.lsr_end = new_start;
 307
 308         /* add these two entries to list */
 309         fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
 310         fld_cache_entry_add(cache, fldt, &f_new->fce_list);
 311
 312         /* no need to fixup */
 313         EXIT;
 314 }
 315
 316 /**
 317  * handle range overlap in fld cache.
 318  */
 319 void fld_cache_overlap_handle(struct fld_cache *cache,
 320                               struct fld_cache_entry *f_curr,
 321                               struct fld_cache_entry *f_new)
 322 {
 323         const struct lu_seq_range *range = &f_new->fce_range;
 324         const seqno_t new_start  = range->lsr_start;
 325         const seqno_t new_end  = range->lsr_end;
 326         const mdsno_t mdt = range->lsr_index;
 327
 328         /* this is overlap case, these case are checking overlapping with
 329          * prev range only. fixup will handle overlaping with next range. */
 330
 331         if (f_curr->fce_range.lsr_index == mdt) {
 332                 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
 333                                                   new_start);
 334
 335                 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
 336                                                 new_end);
 337
 338                 OBD_FREE_PTR(f_new);
 339                 fld_fix_new_list(cache);
 340
 341         } else if (new_start <= f_curr->fce_range.lsr_start &&
 342                         f_curr->fce_range.lsr_end <= new_end) {
 343                 /* case 1: new range completely overshadowed existing range.
 344                  *         e.g. whole range migrated. update fld cache entry */
 345
 346                 f_curr->fce_range = *range;
 347                 OBD_FREE_PTR(f_new);
 348                 fld_fix_new_list(cache);
 349
 350         } else if (f_curr->fce_range.lsr_start < new_start &&
 351                         new_end < f_curr->fce_range.lsr_end) {
 352                 /* case 2: new range fit within existing range. */
 353
 354                 fld_cache_punch_hole(cache, f_curr, f_new);
 355
 356         } else  if (new_end <= f_curr->fce_range.lsr_end) {
 357                 /* case 3: overlap:
 358                  *         [new_start [c_start  new_end)  c_end)
 359                  */
 360
 361                 LASSERT(new_start <= f_curr->fce_range.lsr_start);
 362
 363                 f_curr->fce_range.lsr_start = new_end;
 364                 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
 365
 366         } else if (f_curr->fce_range.lsr_start <= new_start) {
 367                 /* case 4: overlap:
 368                  *         [c_start [new_start c_end) new_end)
 369                  */
 370
 371                 LASSERT(f_curr->fce_range.lsr_end <= new_end);
 372
 373                 f_curr->fce_range.lsr_end = new_start;
 374                 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
 375         } else
 376                 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
 377                        PRANGE(range),PRANGE(&f_curr->fce_range));
 378 }
 379
 380 /**
 381  * Insert FLD entry in FLD cache.
 382  *
 383  * This function handles all cases of merging and breaking up of
 384  * ranges.
 385  */
 386 void fld_cache_insert(struct fld_cache *cache,
 387                       const struct lu_seq_range *range)
 388 {
 389         struct fld_cache_entry *f_new;
 390         struct fld_cache_entry *f_curr;
 391         struct fld_cache_entry *n;
 392         cfs_list_t *head;
 393         cfs_list_t *prev = NULL;
 394         const seqno_t new_start  = range->lsr_start;
 395         const seqno_t new_end  = range->lsr_end;
 396         __u32 new_flags  = range->lsr_flags;
 397         ENTRY;
 398
 399         LASSERT(range_is_sane(range));
 400
 401         /* Allocate new entry. */
 402         OBD_ALLOC_PTR(f_new);
 403         if (!f_new) {
 404                 EXIT;
 405                 return;
 406         }
 407
 408         f_new->fce_range = *range;
 409
 410         /*
 411          * Duplicate entries are eliminated in inset op.
 412          * So we don't need to search new entry before starting insertion loop.
 413          */
 414
 415         cfs_spin_lock(&cache->fci_lock);
 416         fld_cache_shrink(cache);
 417
 418         head = &cache->fci_entries_head;
 419
 420         cfs_list_for_each_entry_safe(f_curr, n, head, fce_list) {
 421                 /* add list if next is end of list */
 422                 if (new_end < f_curr->fce_range.lsr_start ||
 423                    (new_end == f_curr->fce_range.lsr_start &&
 424                     new_flags != f_curr->fce_range.lsr_flags))
 425                         break;
 426
 427                 prev = &f_curr->fce_list;
 428                 /* check if this range is to left of new range. */
 429                 if (new_start < f_curr->fce_range.lsr_end &&
 430                     new_flags == f_curr->fce_range.lsr_flags) {
 431                         fld_cache_overlap_handle(cache, f_curr, f_new);
 432                         goto out;
 433                 }
 434         }
 435
 436         if (prev == NULL)
 437                 prev = head;
 438
 439         CDEBUG(D_INFO, "insert range "DRANGE"\n", PRANGE(&f_new->fce_range));
 440         /* Add new entry to cache and lru list. */
 441         fld_cache_entry_add(cache, f_new, prev);
 442 out:
 443         cfs_spin_unlock(&cache->fci_lock);
 444         EXIT;
 445 }
 446
 447 /**
 448  * lookup \a seq sequence for range in fld cache.
 449  */
 450 int fld_cache_lookup(struct fld_cache *cache,
 451                      const seqno_t seq, struct lu_seq_range *range)
 452 {
 453         struct fld_cache_entry *flde;
 454         cfs_list_t *head;
 455         ENTRY;
 456
 457
 458         cfs_spin_lock(&cache->fci_lock);
 459         head = &cache->fci_entries_head;
 460
 461         cache->fci_stat.fst_count++;
 462         cfs_list_for_each_entry(flde, head, fce_list) {
 463                 if (flde->fce_range.lsr_start > seq)
 464                         break;
 465
 466                 if (range_within(&flde->fce_range, seq)) {
 467                         *range = flde->fce_range;
 468
 469                         /* update position of this entry in lru list. */
 470                         cfs_list_move(&flde->fce_lru, &cache->fci_lru);
 471                         cache->fci_stat.fst_cache++;
 472                         cfs_spin_unlock(&cache->fci_lock);
 473                         RETURN(0);
 474                 }
 475         }
 476         cfs_spin_unlock(&cache->fci_lock);
 477         RETURN(-ENOENT);
 478 }