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