lustre/fld/fld_cache.c

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