4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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
22 * Copyright 2020, DataDirect Networks Storage.
24 * This file is part of Lustre, http://www.lustre.org/
26 * Author: John L. Hammond <jhammond@whamcloud.com>
28 * lustre/utils/ofd_access_batch.c
30 * Access log entry batching for ofd_access_log_reader.
39 #include <linux/lustre/lustre_access_log.h>
40 #include <linux/lustre/lustre_fid.h>
41 #include <linux/lustre/lustre_idl.h>
42 #include <libcfs/util/hash.h>
43 #include <libcfs/util/list.h>
45 #include "ofd_access_batch.h"
47 /* XXX Weird param order to be consistent with list_replace_init(). */
48 static inline void list_replace_init(struct list_head *old_node,
49 struct list_head *new_node)
51 list_add(new_node, old_node);
52 list_del_init(old_node);
55 struct fid_hash_node {
56 struct list_head fhn_node;
57 struct lu_fid fhn_fid;
60 static inline bool fid_eq(const struct lu_fid *f1, const struct lu_fid *f2)
62 return f1->f_seq == f2->f_seq && f1->f_oid == f2->f_oid &&
63 f1->f_ver == f2->f_ver;
66 static inline __u64 fid_flatten(const struct lu_fid *fid)
71 if (fid_is_igif(fid)) {
72 ino = lu_igif_ino(fid);
78 ino = (seq << 24) + ((seq >> 24) & 0xffffff0000ULL) + fid_oid(fid);
80 return ino != 0 ? ino : fid_oid(fid);
84 * map fid to 32 bit value for ino on 32bit systems.
86 static inline __u32 fid_flatten32(const struct lu_fid *fid)
91 if (fid_is_igif(fid)) {
92 ino = lu_igif_ino(fid);
96 seq = fid_seq(fid) - FID_SEQ_START;
98 /* Map the high bits of the OID into higher bits of the inode number so
99 * that inodes generated at about the same time have a reduced chance
100 * of collisions. This will give a period of 2^12 = 1024 unique clients
101 * (from SEQ) and up to min(LUSTRE_SEQ_MAX_WIDTH, 2^20) = 128k objects
102 * (from OID), or up to 128M inodes without collisions for new files.
104 ino = ((seq & 0x000fffffULL) << 12) + ((seq >> 8) & 0xfffff000) +
105 (seq >> (64 - (40-8)) & 0xffffff00) +
106 (fid_oid(fid) & 0xff000fff) + ((fid_oid(fid) & 0x00fff000) << 8);
108 return ino != 0 ? ino : fid_oid(fid);
111 static unsigned long fid_hash(const struct lu_fid *f, unsigned int shift)
113 #if __BITS_PER_LONG == 32
114 return hash_long(fid_flatten32(f), shift);
115 #elif __BITS_PER_LONG == 64
116 return hash_long(fid_flatten(f), shift);
118 # error "Wordsize not 32 or 64"
122 static void fhn_init(struct fid_hash_node *fhn, const struct lu_fid *fid)
124 INIT_LIST_HEAD(&fhn->fhn_node);
128 static bool fhn_is_hashed(struct fid_hash_node *fhn)
130 return !list_empty(&fhn->fhn_node);
133 static void fhn_del_init(struct fid_hash_node *fhn)
135 if (fhn_is_hashed(fhn))
136 list_del_init(&fhn->fhn_node);
139 static inline void fhn_replace_init(struct fid_hash_node *old_fhn,
140 struct fid_hash_node *new_fhn)
142 list_add(&new_fhn->fhn_node, &old_fhn->fhn_node);
143 list_del_init(&old_fhn->fhn_node);
146 void fid_hash_add(struct list_head *head, unsigned int shift,
147 struct fid_hash_node *fhn)
149 assert(!fhn_is_hashed(fhn));
151 list_add(&fhn->fhn_node, &head[fid_hash(&fhn->fhn_fid, shift)]);
154 struct fid_hash_node *
155 fid_hash_find(struct list_head *head, unsigned int shift, const struct lu_fid *fid)
157 struct list_head *hash_list;
158 struct fid_hash_node *fhn, *next;
160 hash_list = &head[fid_hash(fid, shift)];
161 list_for_each_entry_safe(fhn, next, hash_list, fhn_node) {
162 assert(fhn_is_hashed(fhn));
164 if (fid_eq(fid, &fhn->fhn_fid))
171 struct fid_hash_node *
172 fid_hash_insert(struct list_head *head, unsigned int shift, struct fid_hash_node *new_fhn)
174 struct list_head *list;
175 struct fid_hash_node *old_fhn, *next;
177 list = &head[fid_hash(&new_fhn->fhn_fid, shift)];
178 list_for_each_entry_safe(old_fhn, next, list, fhn_node) {
179 assert(fhn_is_hashed(old_fhn));
181 if (fid_eq(&old_fhn->fhn_fid, &new_fhn->fhn_fid))
185 list_add(&new_fhn->fhn_node, list);
190 int fid_hash_init(struct list_head **phead, unsigned int *pshift, unsigned int shift)
192 struct list_head *new_head;
195 new_head = malloc(sizeof(*new_head) << shift);
196 if (new_head == NULL)
199 for (i = 0; i < (1 << shift); i++)
200 INIT_LIST_HEAD(&new_head[i]);
208 int fid_hash_resize(struct list_head **phead, unsigned int *pshift, unsigned int new_shift)
210 struct list_head *new_head;
214 if (*pshift == new_shift)
217 rc = fid_hash_init(&new_head, &new_shift, new_shift);
221 for (i = 0; i < (1 << *pshift); i++) {
222 struct list_head *list = &(*phead)[i];
223 struct fid_hash_node *fhn, *next;
225 list_for_each_entry_safe(fhn, next, list, fhn_node) {
227 fid_hash_add(new_head, new_shift, fhn);
243 /* Entry in the batching hash. */
245 struct fid_hash_node alre_fid_hash_node;
246 time_t alre_time[2]; /* Not strictly needed. */
250 __u64 alre_segment_count[2];
252 char alre_obd_name[];
256 ALR_BATCH_HASH_SHIFT_DEFAULT = 10,
257 ALR_BATCH_HASH_SHIFT_MAX = 30,
261 struct list_head *alrb_hash;
262 unsigned int alrb_hash_shift;
263 unsigned int alrb_count;
266 static void alre_del_init(struct alr_entry *alre)
268 fhn_del_init(&alre->alre_fid_hash_node);
271 static void alre_update(struct alr_entry *alre, time_t time, __u64 begin,
272 __u64 end, __u32 size, __u32 segment_count, __u32 flags)
274 unsigned int d = (flags & OFD_ACCESS_READ) ? ALR_READ : ALR_WRITE;
276 alre->alre_time[d] = max_t(time_t, alre->alre_time[d], time);
277 alre->alre_begin[d] = min_t(__u64, alre->alre_begin[d], begin);
278 alre->alre_end[d] = max_t(__u64, alre->alre_end[d], end);
279 alre->alre_size[d] += size;
280 alre->alre_segment_count[d] += segment_count;
281 alre->alre_count[d] += 1;
284 int alr_batch_add(struct alr_batch *alrb, const char *obd_name,
285 const struct lu_fid *pfid, time_t time, __u64 begin, __u64 end,
286 __u32 size, __u32 segment_count, __u32 flags)
288 struct fid_hash_node fhn, *p;
289 struct alr_entry *alre;
295 assert(sizeof(time_t) == sizeof(__u64));
297 fhn_init(&fhn, pfid);
299 /* Find old or insert sentinel (fhn). Replace sentinel if returned. */
300 p = fid_hash_insert(alrb->alrb_hash, alrb->alrb_hash_shift, &fhn);
302 size_t alre_size = sizeof(*alre) + strlen(obd_name) + 1;
304 alre = calloc(1, alre_size);
310 fhn_init(&alre->alre_fid_hash_node, pfid);
311 strcpy(alre->alre_obd_name, obd_name);
312 fhn_replace_init(&fhn, &alre->alre_fid_hash_node);
315 alre = container_of(p, struct alr_entry, alre_fid_hash_node);
318 alre_update(alre, time, begin, end, size, segment_count, flags);
326 int sort_compare(const void *a1, const void *a2)
328 int l = *(const int*)a1;
329 int r = *(const int *)a2;
330 if (l > r) return -1;
335 static void alre_printf(FILE *f, struct alr_entry *alre, int d)
337 fprintf(f, "o=%s f="DFID" t=%lld b=%llu e=%llu s=%llu g=%llu n=%llu d=%c\n",
339 PFID(&alre->alre_fid_hash_node.fhn_fid),
340 (long long)alre->alre_time[d],
341 (unsigned long long)alre->alre_begin[d],
342 (unsigned long long)alre->alre_end[d],
343 (unsigned long long)alre->alre_size[d],
344 (unsigned long long)alre->alre_segment_count[d],
345 (unsigned long long)alre->alre_count[d],
346 (d == ALR_READ) ? 'r' : 'w');
349 struct alr_thread_arg {
350 struct list_head list;
355 void *alr_sort_and_print_thread(void *arg)
357 struct alr_entry *alre, *next;
358 struct alr_thread_arg *aa = arg;
359 struct list_head *tmp = &aa->list;
360 int *sa, d, i, nr = 0;
363 list_for_each_entry(alre, tmp, alre_fid_hash_node.fhn_node) {
364 if (alre->alre_count[0] > 0)
366 if (alre->alre_count[1] > 0)
370 sa = calloc(sizeof(int), nr);
372 fprintf(stderr, "cannot allocate memory for sorting\n");
376 list_for_each_entry(alre, tmp, alre_fid_hash_node.fhn_node) {
377 if (alre->alre_count[0] > 0)
378 sa[i++] = alre->alre_count[0];
379 if (alre->alre_count[1] > 0)
380 sa[i++] = alre->alre_count[1];
382 qsort(sa, nr, sizeof(int), sort_compare);
383 i = nr * aa->fraction / 100;
391 /* there might be lots of items at @cut, but we want to limit total
392 * output. so the first loop dumps all items > @cut and the second
393 * loop dumps items=@cut so that total number (@i) is not exceeeded.
394 * XXX: possible optimization - move items=@cut to another list, so
395 * that 2nd pass takes < O(n) */
396 list_for_each_entry_safe(alre, next, tmp, alre_fid_hash_node.fhn_node) {
397 for (d = 0; d < 2; d++) {
398 if (alre->alre_count[d] <= cut)
400 alre_printf(aa->file, alre, d);
404 list_for_each_entry_safe(alre, next, tmp, alre_fid_hash_node.fhn_node) {
405 for (d = 0; d < 2 && i > 0; d++) {
406 if (alre->alre_count[d] != cut)
408 alre_printf(aa->file, alre, d);
417 pthread_exit((void *)0);
422 /* Print, clear, and resize the batch. */
423 int alr_batch_print(struct alr_batch *alrb, FILE *file, int fraction)
425 unsigned int new_hash_shift;
426 struct alr_thread_arg *aa;
433 aa = malloc(sizeof(*aa));
437 /* move all collected items to the temp list */
438 INIT_LIST_HEAD(&aa->list);
439 for (i = 0; i < (1 << alrb->alrb_hash_shift); i++) {
440 if (list_empty(&alrb->alrb_hash[i]))
442 list_splice(&alrb->alrb_hash[i], &aa->list);
443 INIT_LIST_HEAD(&alrb->alrb_hash[i]);
446 aa->fraction = fraction;
448 /* as sorting may take time and we don't want to lose access
449 * records we better do sorting and printing in a different thread */
450 rc = pthread_create(&pid, NULL, alr_sort_and_print_thread, aa);
452 /* Resize hash based on previous count. */
453 new_hash_shift = alrb->alrb_hash_shift;
455 while (new_hash_shift < ALR_BATCH_HASH_SHIFT_MAX &&
456 (1 << new_hash_shift) < alrb->alrb_count)
459 fid_hash_resize(&alrb->alrb_hash, &alrb->alrb_hash_shift,
462 alrb->alrb_count = 0;
467 struct alr_batch *alr_batch_create(unsigned int shift)
469 struct alr_batch *alrb;
473 shift = ALR_BATCH_HASH_SHIFT_DEFAULT;
475 alrb = calloc(1, sizeof(*alrb));
479 rc = fid_hash_init(&alrb->alrb_hash, &alrb->alrb_hash_shift, shift);
488 void alr_batch_destroy(struct alr_batch *alrb)
495 for (i = 0; i < (1 << alrb->alrb_hash_shift); i++) {
496 struct list_head *list = &alrb->alrb_hash[i];
497 struct alr_entry *alre, *next;
499 list_for_each_entry_safe(alre, next, list, alre_fid_hash_node.fhn_node) {
505 free(alrb->alrb_hash);