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