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  * Copyright (c) 2012, 2013, Intel Corporation.
  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 #define DEBUG_SUBSYSTEM S_FLD
  45
  46 #ifdef __KERNEL__
  47 # include <libcfs/libcfs.h>
  48 # include <linux/module.h>
  49 # include <linux/jbd.h>
  50 # include <asm/div64.h>
  51 #else /* __KERNEL__ */
  52 # include <liblustre.h>
  53 # include <libcfs/list.h>
  54 #endif
  55
  56 #include <obd.h>
  57 #include <obd_class.h>
  58 #include <lustre_ver.h>
  59 #include <obd_support.h>
  60 #include <lprocfs_status.h>
  61
  62 #include <dt_object.h>
  63 #include <md_object.h>
  64 #include <lustre_req_layout.h>
  65 #include <lustre_fld.h>
  66 #include "fld_internal.h"
  67
  68 /**
  69  * create fld cache.
  70  */
  71 struct fld_cache *fld_cache_init(const char *name,
  72                                  int cache_size, int cache_threshold)
  73 {
  74         struct fld_cache *cache;
  75         ENTRY;
  76
  77         LASSERT(name != NULL);
  78         LASSERT(cache_threshold < cache_size);
  79
  80         OBD_ALLOC_PTR(cache);
  81         if (cache == NULL)
  82                 RETURN(ERR_PTR(-ENOMEM));
  83
  84         CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
  85         CFS_INIT_LIST_HEAD(&cache->fci_lru);
  86
  87         cache->fci_cache_count = 0;
  88         spin_lock_init(&cache->fci_lock);
  89
  90         strncpy(cache->fci_name, name,
  91                 sizeof(cache->fci_name));
  92
  93         cache->fci_cache_size = cache_size;
  94         cache->fci_threshold = cache_threshold;
  95
  96         /* Init fld cache info. */
  97         memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
  98
  99         CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
 100                cache->fci_name, cache_size, cache_threshold);
 101
 102         RETURN(cache);
 103 }
 104
 105 /**
 106  * destroy fld cache.
 107  */
 108 void fld_cache_fini(struct fld_cache *cache)
 109 {
 110         __u64 pct;
 111         ENTRY;
 112
 113         LASSERT(cache != NULL);
 114         fld_cache_flush(cache);
 115
 116         if (cache->fci_stat.fst_count > 0) {
 117                 pct = cache->fci_stat.fst_cache * 100;
 118                 do_div(pct, cache->fci_stat.fst_count);
 119         } else {
 120                 pct = 0;
 121         }
 122
 123         CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
 124         CDEBUG(D_INFO, "  Total reqs: "LPU64"\n", cache->fci_stat.fst_count);
 125         CDEBUG(D_INFO, "  Cache reqs: "LPU64"\n", cache->fci_stat.fst_cache);
 126         CDEBUG(D_INFO, "  Cache hits: "LPU64"%%\n", pct);
 127
 128         OBD_FREE_PTR(cache);
 129
 130         EXIT;
 131 }
 132
 133 /**
 134  * delete given node from list.
 135  */
 136 void fld_cache_entry_delete(struct fld_cache *cache,
 137                             struct fld_cache_entry *node)
 138 {
 139         cfs_list_del(&node->fce_list);
 140         cfs_list_del(&node->fce_lru);
 141         cache->fci_cache_count--;
 142         OBD_FREE_PTR(node);
 143 }
 144
 145 /**
 146  * fix list by checking new entry with NEXT entry in order.
 147  */
 148 static void fld_fix_new_list(struct fld_cache *cache)
 149 {
 150         struct fld_cache_entry *f_curr;
 151         struct fld_cache_entry *f_next;
 152         struct lu_seq_range *c_range;
 153         struct lu_seq_range *n_range;
 154         cfs_list_t *head = &cache->fci_entries_head;
 155         ENTRY;
 156
 157 restart_fixup:
 158
 159         cfs_list_for_each_entry_safe(f_curr, f_next, head, fce_list) {
 160                 c_range = &f_curr->fce_range;
 161                 n_range = &f_next->fce_range;
 162
 163                 LASSERT(range_is_sane(c_range));
 164                 if (&f_next->fce_list == head)
 165                         break;
 166
 167                 if (c_range->lsr_flags != n_range->lsr_flags)
 168                         continue;
 169
 170                 LASSERTF(c_range->lsr_start <= n_range->lsr_start,
 171                          "cur lsr_start "DRANGE" next lsr_start "DRANGE"\n",
 172                          PRANGE(c_range), PRANGE(n_range));
 173
 174                 /* check merge possibility with next range */
 175                 if (c_range->lsr_end == n_range->lsr_start) {
 176                         if (c_range->lsr_index != n_range->lsr_index)
 177                                 continue;
 178                         n_range->lsr_start = c_range->lsr_start;
 179                         fld_cache_entry_delete(cache, f_curr);
 180                         continue;
 181                 }
 182
 183                 /* check if current range overlaps with next range. */
 184                 if (n_range->lsr_start < c_range->lsr_end) {
 185                         if (c_range->lsr_index == n_range->lsr_index) {
 186                                 n_range->lsr_start = c_range->lsr_start;
 187                                 n_range->lsr_end = max(c_range->lsr_end,
 188                                                        n_range->lsr_end);
 189                                 fld_cache_entry_delete(cache, f_curr);
 190                         } else {
 191                                 if (n_range->lsr_end <= c_range->lsr_end) {
 192                                         *n_range = *c_range;
 193                                         fld_cache_entry_delete(cache, f_curr);
 194                                 } else
 195                                         n_range->lsr_start = c_range->lsr_end;
 196                         }
 197
 198                         /* we could have overlap over next
 199                          * range too. better restart. */
 200                         goto restart_fixup;
 201                 }
 202
 203                 /* kill duplicates */
 204                 if (c_range->lsr_start == n_range->lsr_start &&
 205                     c_range->lsr_end == n_range->lsr_end)
 206                         fld_cache_entry_delete(cache, f_curr);
 207         }
 208
 209         EXIT;
 210 }
 211
 212 /**
 213  * add node to fld cache
 214  */
 215 static inline void fld_cache_entry_add(struct fld_cache *cache,
 216                                        struct fld_cache_entry *f_new,
 217                                        cfs_list_t *pos)
 218 {
 219         cfs_list_add(&f_new->fce_list, pos);
 220         cfs_list_add(&f_new->fce_lru, &cache->fci_lru);
 221
 222         cache->fci_cache_count++;
 223         fld_fix_new_list(cache);
 224 }
 225
 226 /**
 227  * Check if cache needs to be shrunk. If so - do it.
 228  * Remove one entry in list and so on until cache is shrunk enough.
 229  */
 230 static int fld_cache_shrink(struct fld_cache *cache)
 231 {
 232         struct fld_cache_entry *flde;
 233         cfs_list_t *curr;
 234         int num = 0;
 235         ENTRY;
 236
 237         LASSERT(cache != NULL);
 238
 239         if (cache->fci_cache_count < cache->fci_cache_size)
 240                 RETURN(0);
 241
 242         curr = cache->fci_lru.prev;
 243
 244         while (cache->fci_cache_count + cache->fci_threshold >
 245                cache->fci_cache_size && curr != &cache->fci_lru) {
 246
 247                 flde = cfs_list_entry(curr, struct fld_cache_entry, fce_lru);
 248                 curr = curr->prev;
 249                 fld_cache_entry_delete(cache, flde);
 250                 num++;
 251         }
 252
 253         CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
 254                "%d entries\n", cache->fci_name, num);
 255
 256         RETURN(0);
 257 }
 258
 259 /**
 260  * kill all fld cache entries.
 261  */
 262 void fld_cache_flush(struct fld_cache *cache)
 263 {
 264         ENTRY;
 265
 266         spin_lock(&cache->fci_lock);
 267         cache->fci_cache_size = 0;
 268         fld_cache_shrink(cache);
 269         spin_unlock(&cache->fci_lock);
 270
 271         EXIT;
 272 }
 273
 274 /**
 275  * punch hole in existing range. divide this range and add new
 276  * entry accordingly.
 277  */
 278
 279 void fld_cache_punch_hole(struct fld_cache *cache,
 280                           struct fld_cache_entry *f_curr,
 281                           struct fld_cache_entry *f_new)
 282 {
 283         const struct lu_seq_range *range = &f_new->fce_range;
 284         const seqno_t new_start  = range->lsr_start;
 285         const seqno_t new_end  = range->lsr_end;
 286         struct fld_cache_entry *fldt;
 287
 288         ENTRY;
 289         OBD_ALLOC_GFP(fldt, sizeof *fldt, CFS_ALLOC_ATOMIC);
 290         if (!fldt) {
 291                 OBD_FREE_PTR(f_new);
 292                 EXIT;
 293                 /* overlap is not allowed, so dont mess up list. */
 294                 return;
 295         }
 296         /*  break f_curr RANGE into three RANGES:
 297          *        f_curr, f_new , fldt
 298          */
 299
 300         /* f_new = *range */
 301
 302         /* fldt */
 303         fldt->fce_range.lsr_start = new_end;
 304         fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
 305         fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
 306
 307         /* f_curr */
 308         f_curr->fce_range.lsr_end = new_start;
 309
 310         /* add these two entries to list */
 311         fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
 312         fld_cache_entry_add(cache, fldt, &f_new->fce_list);
 313
 314         /* no need to fixup */
 315         EXIT;
 316 }
 317
 318 /**
 319  * handle range overlap in fld cache.
 320  */
 321 static void fld_cache_overlap_handle(struct fld_cache *cache,
 322                                 struct fld_cache_entry *f_curr,
 323                                 struct fld_cache_entry *f_new)
 324 {
 325         const struct lu_seq_range *range = &f_new->fce_range;
 326         const seqno_t new_start  = range->lsr_start;
 327         const seqno_t new_end  = range->lsr_end;
 328         const mdsno_t mdt = range->lsr_index;
 329
 330         /* this is overlap case, these case are checking overlapping with
 331          * prev range only. fixup will handle overlaping with next range. */
 332
 333         if (f_curr->fce_range.lsr_index == mdt) {
 334                 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
 335                                                   new_start);
 336
 337                 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
 338                                                 new_end);
 339
 340                 OBD_FREE_PTR(f_new);
 341                 fld_fix_new_list(cache);
 342
 343         } else if (new_start <= f_curr->fce_range.lsr_start &&
 344                         f_curr->fce_range.lsr_end <= new_end) {
 345                 /* case 1: new range completely overshadowed existing range.
 346                  *         e.g. whole range migrated. update fld cache entry */
 347
 348                 f_curr->fce_range = *range;
 349                 OBD_FREE_PTR(f_new);
 350                 fld_fix_new_list(cache);
 351
 352         } else if (f_curr->fce_range.lsr_start < new_start &&
 353                         new_end < f_curr->fce_range.lsr_end) {
 354                 /* case 2: new range fit within existing range. */
 355
 356                 fld_cache_punch_hole(cache, f_curr, f_new);
 357
 358         } else  if (new_end <= f_curr->fce_range.lsr_end) {
 359                 /* case 3: overlap:
 360                  *         [new_start [c_start  new_end)  c_end)
 361                  */
 362
 363                 LASSERT(new_start <= f_curr->fce_range.lsr_start);
 364
 365                 f_curr->fce_range.lsr_start = new_end;
 366                 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
 367
 368         } else if (f_curr->fce_range.lsr_start <= new_start) {
 369                 /* case 4: overlap:
 370                  *         [c_start [new_start c_end) new_end)
 371                  */
 372
 373                 LASSERT(f_curr->fce_range.lsr_end <= new_end);
 374
 375                 f_curr->fce_range.lsr_end = new_start;
 376                 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
 377         } else
 378                 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
 379                        PRANGE(range),PRANGE(&f_curr->fce_range));
 380 }
 381
 382 struct fld_cache_entry
 383 *fld_cache_entry_create(const struct lu_seq_range *range)
 384 {
 385         struct fld_cache_entry *f_new;
 386
 387         LASSERT(range_is_sane(range));
 388
 389         OBD_ALLOC_PTR(f_new);
 390         if (!f_new)
 391                 RETURN(ERR_PTR(-ENOMEM));
 392
 393         f_new->fce_range = *range;
 394         RETURN(f_new);
 395 }
 396
 397 /**
 398  * Insert FLD entry in FLD cache.
 399  *
 400  * This function handles all cases of merging and breaking up of
 401  * ranges.
 402  */
 403 int fld_cache_insert_nolock(struct fld_cache *cache,
 404                             struct fld_cache_entry *f_new)
 405 {
 406         struct fld_cache_entry *f_curr;
 407         struct fld_cache_entry *n;
 408         cfs_list_t *head;
 409         cfs_list_t *prev = NULL;
 410         const seqno_t new_start  = f_new->fce_range.lsr_start;
 411         const seqno_t new_end  = f_new->fce_range.lsr_end;
 412         __u32 new_flags  = f_new->fce_range.lsr_flags;
 413         ENTRY;
 414
 415         LASSERT_SPIN_LOCKED(&cache->fci_lock);
 416
 417         /*
 418          * Duplicate entries are eliminated in insert op.
 419          * So we don't need to search new entry before starting
 420          * insertion loop.
 421          */
 422
 423         if (!cache->fci_no_shrink)
 424                 fld_cache_shrink(cache);
 425
 426         head = &cache->fci_entries_head;
 427
 428         cfs_list_for_each_entry_safe(f_curr, n, head, fce_list) {
 429                 /* add list if next is end of list */
 430                 if (new_end < f_curr->fce_range.lsr_start ||
 431                    (new_end == f_curr->fce_range.lsr_start &&
 432                     new_flags != f_curr->fce_range.lsr_flags))
 433                         break;
 434
 435                 prev = &f_curr->fce_list;
 436                 /* check if this range is to left of new range. */
 437                 if (new_start < f_curr->fce_range.lsr_end &&
 438                     new_flags == f_curr->fce_range.lsr_flags) {
 439                         fld_cache_overlap_handle(cache, f_curr, f_new);
 440                         goto out;
 441                 }
 442         }
 443
 444         if (prev == NULL)
 445                 prev = head;
 446
 447         CDEBUG(D_INFO, "insert range "DRANGE"\n", PRANGE(&f_new->fce_range));
 448         /* Add new entry to cache and lru list. */
 449         fld_cache_entry_add(cache, f_new, prev);
 450 out:
 451         RETURN(0);
 452 }
 453
 454 int fld_cache_insert(struct fld_cache *cache,
 455                      const struct lu_seq_range *range)
 456 {
 457         struct fld_cache_entry  *flde;
 458         int rc;
 459
 460         flde = fld_cache_entry_create(range);
 461         if (IS_ERR(flde))
 462                 RETURN(PTR_ERR(flde));
 463
 464         spin_lock(&cache->fci_lock);
 465         rc = fld_cache_insert_nolock(cache, flde);
 466         spin_unlock(&cache->fci_lock);
 467         if (rc)
 468                 OBD_FREE_PTR(flde);
 469
 470         RETURN(rc);
 471 }
 472
 473 void fld_cache_delete_nolock(struct fld_cache *cache,
 474                       const struct lu_seq_range *range)
 475 {
 476         struct fld_cache_entry *flde;
 477         struct fld_cache_entry *tmp;
 478         cfs_list_t *head;
 479
 480         LASSERT_SPIN_LOCKED(&cache->fci_lock);
 481         head = &cache->fci_entries_head;
 482         cfs_list_for_each_entry_safe(flde, tmp, head, fce_list) {
 483                 /* add list if next is end of list */
 484                 if (range->lsr_start == flde->fce_range.lsr_start ||
 485                    (range->lsr_end == flde->fce_range.lsr_end &&
 486                     range->lsr_flags == flde->fce_range.lsr_flags)) {
 487                         fld_cache_entry_delete(cache, flde);
 488                         break;
 489                 }
 490         }
 491 }
 492
 493 /**
 494  * Delete FLD entry in FLD cache.
 495  *
 496  */
 497 void fld_cache_delete(struct fld_cache *cache,
 498                       const struct lu_seq_range *range)
 499 {
 500         spin_lock(&cache->fci_lock);
 501         fld_cache_delete_nolock(cache, range);
 502         spin_unlock(&cache->fci_lock);
 503 }
 504
 505 struct fld_cache_entry
 506 *fld_cache_entry_lookup_nolock(struct fld_cache *cache,
 507                               struct lu_seq_range *range)
 508 {
 509         struct fld_cache_entry *flde;
 510         struct fld_cache_entry *got = NULL;
 511         cfs_list_t *head;
 512
 513         LASSERT_SPIN_LOCKED(&cache->fci_lock);
 514         head = &cache->fci_entries_head;
 515         cfs_list_for_each_entry(flde, head, fce_list) {
 516                 if (range->lsr_start == flde->fce_range.lsr_start ||
 517                    (range->lsr_end == flde->fce_range.lsr_end &&
 518                     range->lsr_flags == flde->fce_range.lsr_flags)) {
 519                         got = flde;
 520                         break;
 521                 }
 522         }
 523
 524         RETURN(got);
 525 }
 526
 527 /**
 528  * lookup \a seq sequence for range in fld cache.
 529  */
 530 struct fld_cache_entry
 531 *fld_cache_entry_lookup(struct fld_cache *cache, struct lu_seq_range *range)
 532 {
 533         struct fld_cache_entry *got = NULL;
 534         ENTRY;
 535
 536         spin_lock(&cache->fci_lock);
 537         got = fld_cache_entry_lookup_nolock(cache, range);
 538         spin_unlock(&cache->fci_lock);
 539         RETURN(got);
 540 }
 541
 542 /**
 543  * lookup \a seq sequence for range in fld cache.
 544  */
 545 int fld_cache_lookup(struct fld_cache *cache,
 546                      const seqno_t seq, struct lu_seq_range *range)
 547 {
 548         struct fld_cache_entry *flde;
 549         struct fld_cache_entry *prev = NULL;
 550         cfs_list_t *head;
 551         ENTRY;
 552
 553         spin_lock(&cache->fci_lock);
 554         head = &cache->fci_entries_head;
 555
 556         cache->fci_stat.fst_count++;
 557         cfs_list_for_each_entry(flde, head, fce_list) {
 558                 if (flde->fce_range.lsr_start > seq) {
 559                         if (prev != NULL)
 560                                 memcpy(range, prev, sizeof(*range));
 561                         break;
 562                 }
 563
 564                 prev = flde;
 565                 if (range_within(&flde->fce_range, seq)) {
 566                         *range = flde->fce_range;
 567
 568                         /* update position of this entry in lru list. */
 569                         cfs_list_move(&flde->fce_lru, &cache->fci_lru);
 570                         cache->fci_stat.fst_cache++;
 571                         spin_unlock(&cache->fci_lock);
 572                         RETURN(0);
 573                 }
 574         }
 575         spin_unlock(&cache->fci_lock);
 576         RETURN(-ENOENT);
 577 }
 578