Whamcloud - gitweb
LU-13581 build: xarray and lockdep_is_held const clash
[fs/lustre-release.git] / 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         LASSERT(cache != NULL);
92         fld_cache_flush(cache);
93
94         CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
95         CDEBUG(D_INFO, "  Cache reqs: %llu\n", cache->fci_stat.fst_cache);
96         CDEBUG(D_INFO, "  Total reqs: %llu\n", cache->fci_stat.fst_count);
97
98         OBD_FREE_PTR(cache);
99 }
100
101 /**
102  * delete given node from list.
103  */
104 static void fld_cache_entry_delete(struct fld_cache *cache,
105                                    struct fld_cache_entry *node)
106 {
107         list_del(&node->fce_list);
108         list_del(&node->fce_lru);
109         cache->fci_cache_count--;
110         OBD_FREE_PTR(node);
111 }
112
113 /**
114  * fix list by checking new entry with NEXT entry in order.
115  */
116 static void fld_fix_new_list(struct fld_cache *cache)
117 {
118         struct fld_cache_entry *f_curr;
119         struct fld_cache_entry *f_next;
120         struct lu_seq_range *c_range;
121         struct lu_seq_range *n_range;
122         struct list_head *head = &cache->fci_entries_head;
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                         goto restart_fixup;
169                 }
170
171                 /* kill duplicates */
172                 if (c_range->lsr_start == n_range->lsr_start &&
173                     c_range->lsr_end == n_range->lsr_end)
174                         fld_cache_entry_delete(cache, f_curr);
175         }
176
177         EXIT;
178 }
179
180 /**
181  * add node to fld cache
182  */
183 static inline void fld_cache_entry_add(struct fld_cache *cache,
184                                        struct fld_cache_entry *f_new,
185                                        struct list_head *pos)
186 {
187         list_add(&f_new->fce_list, pos);
188         list_add(&f_new->fce_lru, &cache->fci_lru);
189
190         cache->fci_cache_count++;
191         fld_fix_new_list(cache);
192 }
193
194 /**
195  * Check if cache needs to be shrunk. If so - do it.
196  * Remove one entry in list and so on until cache is shrunk enough.
197  */
198 static int fld_cache_shrink(struct fld_cache *cache)
199 {
200         int num = 0;
201
202         ENTRY;
203
204         LASSERT(cache != NULL);
205
206         if (cache->fci_cache_count < cache->fci_cache_size)
207                 RETURN(0);
208
209         while (cache->fci_cache_count + cache->fci_threshold >
210                cache->fci_cache_size &&
211                !list_empty(&cache->fci_lru)) {
212                 struct fld_cache_entry *flde =
213                         list_last_entry(&cache->fci_lru, struct fld_cache_entry,
214                                         fce_lru);
215
216                 fld_cache_entry_delete(cache, flde);
217                 num++;
218         }
219
220         CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
221                "%d entries\n", cache->fci_name, num);
222
223         RETURN(0);
224 }
225
226 /**
227  * kill all fld cache entries.
228  */
229 void fld_cache_flush(struct fld_cache *cache)
230 {
231         ENTRY;
232
233         write_lock(&cache->fci_lock);
234         cache->fci_cache_size = 0;
235         fld_cache_shrink(cache);
236         write_unlock(&cache->fci_lock);
237
238         EXIT;
239 }
240
241 /**
242  * punch hole in existing range. divide this range and add new
243  * entry accordingly.
244  */
245
246 static void fld_cache_punch_hole(struct fld_cache *cache,
247                                  struct fld_cache_entry *f_curr,
248                                  struct fld_cache_entry *f_new)
249 {
250         const struct lu_seq_range *range = &f_new->fce_range;
251         const u64 new_start  = range->lsr_start;
252         const u64 new_end  = range->lsr_end;
253         struct fld_cache_entry *fldt;
254
255         ENTRY;
256         OBD_ALLOC_GFP(fldt, sizeof *fldt, GFP_ATOMIC);
257         if (!fldt) {
258                 OBD_FREE_PTR(f_new);
259                 EXIT;
260                 /* overlap is not allowed, so dont mess up list. */
261                 return;
262         }
263         /*  break f_curr RANGE into three RANGES:
264          *        f_curr, f_new , fldt
265          */
266
267         /* f_new = *range */
268
269         /* fldt */
270         fldt->fce_range.lsr_start = new_end;
271         fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
272         fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
273
274         /* f_curr */
275         f_curr->fce_range.lsr_end = new_start;
276
277         /* add these two entries to list */
278         fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
279         fld_cache_entry_add(cache, fldt, &f_new->fce_list);
280
281         /* no need to fixup */
282         EXIT;
283 }
284
285 /**
286  * handle range overlap in fld cache.
287  */
288 static void fld_cache_overlap_handle(struct fld_cache *cache,
289                                 struct fld_cache_entry *f_curr,
290                                 struct fld_cache_entry *f_new)
291 {
292         const struct lu_seq_range *range = &f_new->fce_range;
293         const u64 new_start  = range->lsr_start;
294         const u64 new_end  = range->lsr_end;
295         const u32 mdt = range->lsr_index;
296
297         /* this is overlap case, these case are checking overlapping with
298          * prev range only. fixup will handle overlaping with next range. */
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                 f_curr->fce_range = *range;
316                 OBD_FREE_PTR(f_new);
317                 fld_fix_new_list(cache);
318
319         } else if (f_curr->fce_range.lsr_start < new_start &&
320                         new_end < f_curr->fce_range.lsr_end) {
321                 /* case 2: new range fit within existing range. */
322
323                 fld_cache_punch_hole(cache, f_curr, f_new);
324
325         } else  if (new_end <= f_curr->fce_range.lsr_end) {
326                 /* case 3: overlap:
327                  *         [new_start [c_start  new_end)  c_end)
328                  */
329
330                 LASSERT(new_start <= f_curr->fce_range.lsr_start);
331
332                 f_curr->fce_range.lsr_start = new_end;
333                 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
334
335         } else if (f_curr->fce_range.lsr_start <= new_start) {
336                 /* case 4: overlap:
337                  *         [c_start [new_start c_end) new_end)
338                  */
339
340                 LASSERT(f_curr->fce_range.lsr_end <= new_end);
341
342                 f_curr->fce_range.lsr_end = new_start;
343                 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
344         } else
345                 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
346                        PRANGE(range),PRANGE(&f_curr->fce_range));
347 }
348
349 struct fld_cache_entry
350 *fld_cache_entry_create(const struct lu_seq_range *range)
351 {
352         struct fld_cache_entry *f_new;
353
354         LASSERT(lu_seq_range_is_sane(range));
355
356         OBD_ALLOC_PTR(f_new);
357         if (!f_new)
358                 RETURN(ERR_PTR(-ENOMEM));
359
360         f_new->fce_range = *range;
361         RETURN(f_new);
362 }
363
364 /**
365  * Insert FLD entry in FLD cache.
366  *
367  * This function handles all cases of merging and breaking up of
368  * ranges.
369  */
370 int fld_cache_insert_nolock(struct fld_cache *cache,
371                             struct fld_cache_entry *f_new)
372 {
373         struct fld_cache_entry *f_curr;
374         struct fld_cache_entry *n;
375         struct list_head *head;
376         struct list_head *prev = NULL;
377         const u64 new_start  = f_new->fce_range.lsr_start;
378         const u64 new_end  = f_new->fce_range.lsr_end;
379         __u32 new_flags  = f_new->fce_range.lsr_flags;
380         ENTRY;
381
382         /*
383          * Duplicate entries are eliminated in insert op.
384          * So we don't need to search new entry before starting
385          * insertion loop.
386          */
387
388         fld_cache_shrink(cache);
389
390         head = &cache->fci_entries_head;
391
392         list_for_each_entry_safe(f_curr, n, head, fce_list) {
393                 /* add list if next is end of list */
394                 if (new_end < f_curr->fce_range.lsr_start ||
395                    (new_end == f_curr->fce_range.lsr_start &&
396                     new_flags != f_curr->fce_range.lsr_flags))
397                         break;
398
399                 prev = &f_curr->fce_list;
400                 /* check if this range is to left of new range. */
401                 if (new_start < f_curr->fce_range.lsr_end &&
402                     new_flags == f_curr->fce_range.lsr_flags) {
403                         fld_cache_overlap_handle(cache, f_curr, f_new);
404                         goto out;
405                 }
406         }
407
408         if (prev == NULL)
409                 prev = head;
410
411         CDEBUG(D_INFO, "insert range "DRANGE"\n", PRANGE(&f_new->fce_range));
412         /* Add new entry to cache and lru list. */
413         fld_cache_entry_add(cache, f_new, prev);
414 out:
415         RETURN(0);
416 }
417
418 int fld_cache_insert(struct fld_cache *cache,
419                      const struct lu_seq_range *range)
420 {
421         struct fld_cache_entry  *flde;
422         int rc;
423
424         flde = fld_cache_entry_create(range);
425         if (IS_ERR(flde))
426                 RETURN(PTR_ERR(flde));
427
428         write_lock(&cache->fci_lock);
429         rc = fld_cache_insert_nolock(cache, flde);
430         write_unlock(&cache->fci_lock);
431         if (rc)
432                 OBD_FREE_PTR(flde);
433
434         RETURN(rc);
435 }
436
437 void fld_cache_delete_nolock(struct fld_cache *cache,
438                       const struct lu_seq_range *range)
439 {
440         struct fld_cache_entry *flde;
441         struct fld_cache_entry *tmp;
442         struct list_head *head;
443
444         head = &cache->fci_entries_head;
445         list_for_each_entry_safe(flde, tmp, head, fce_list) {
446                 /* add list if next is end of list */
447                 if (range->lsr_start == flde->fce_range.lsr_start ||
448                    (range->lsr_end == flde->fce_range.lsr_end &&
449                     range->lsr_flags == flde->fce_range.lsr_flags)) {
450                         fld_cache_entry_delete(cache, flde);
451                         break;
452                 }
453         }
454 }
455
456 /**
457  * lookup \a seq sequence for range in fld cache.
458  */
459 int fld_cache_lookup(struct fld_cache *cache,
460                      const u64 seq, struct lu_seq_range *range)
461 {
462         struct fld_cache_entry *flde;
463         struct fld_cache_entry *prev = NULL;
464         struct list_head *head;
465         ENTRY;
466
467         read_lock(&cache->fci_lock);
468         head = &cache->fci_entries_head;
469
470         cache->fci_stat.fst_count++;
471         list_for_each_entry(flde, head, fce_list) {
472                 if (flde->fce_range.lsr_start > seq) {
473                         if (prev != NULL)
474                                 *range = prev->fce_range;
475                         break;
476                 }
477
478                 prev = flde;
479                 if (lu_seq_range_within(&flde->fce_range, seq)) {
480                         *range = flde->fce_range;
481
482                         cache->fci_stat.fst_cache++;
483                         read_unlock(&cache->fci_lock);
484                         RETURN(0);
485                 }
486         }
487         read_unlock(&cache->fci_lock);
488         RETURN(-ENOENT);
489 }