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