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