// SPDX-License-Identifier: GPL-2.0 /* * Request reply cache. This is currently a global cache, but this may * change in the future and be a per-client cache. * * This code is heavily inspired by the 44BSD implementation, although * it does things a bit differently. * * Copyright (C) 1995, 1996 Olaf Kirch */ #include #include #include #include #include #include #include #include "nfsd.h" #include "cache.h" #define NFSDDBG_FACILITY NFSDDBG_REPCACHE /* * We use this value to determine the number of hash buckets from the max * cache size, the idea being that when the cache is at its maximum number * of entries, then this should be the average number of entries per bucket. */ #define TARGET_BUCKET_SIZE 64 struct nfsd_drc_bucket { struct rb_root rb_head; struct list_head lru_head; spinlock_t cache_lock; }; static struct nfsd_drc_bucket *drc_hashtbl; static struct kmem_cache *drc_slab; /* max number of entries allowed in the cache */ static unsigned int max_drc_entries; /* number of significant bits in the hash value */ static unsigned int maskbits; static unsigned int drc_hashsize; /* * Stats and other tracking of on the duplicate reply cache. All of these and * the "rc" fields in nfsdstats are protected by the cache_lock */ /* total number of entries */ static atomic_t num_drc_entries; /* cache misses due only to checksum comparison failures */ static unsigned int payload_misses; /* amount of memory (in bytes) currently consumed by the DRC */ static unsigned int drc_mem_usage; /* longest hash chain seen */ static unsigned int longest_chain; /* size of cache when we saw the longest hash chain */ static unsigned int longest_chain_cachesize; static int nfsd_cache_append(struct svc_rqst *rqstp, struct kvec *vec); static unsigned long nfsd_reply_cache_count(struct shrinker *shrink, struct shrink_control *sc); static unsigned long nfsd_reply_cache_scan(struct shrinker *shrink, struct shrink_control *sc); static struct shrinker nfsd_reply_cache_shrinker = { .scan_objects = nfsd_reply_cache_scan, .count_objects = nfsd_reply_cache_count, .seeks = 1, }; /* * Put a cap on the size of the DRC based on the amount of available * low memory in the machine. * * 64MB: 8192 * 128MB: 11585 * 256MB: 16384 * 512MB: 23170 * 1GB: 32768 * 2GB: 46340 * 4GB: 65536 * 8GB: 92681 * 16GB: 131072 * * ...with a hard cap of 256k entries. In the worst case, each entry will be * ~1k, so the above numbers should give a rough max of the amount of memory * used in k. */ static unsigned int nfsd_cache_size_limit(void) { unsigned int limit; unsigned long low_pages = totalram_pages - totalhigh_pages; limit = (16 * int_sqrt(low_pages)) << (PAGE_SHIFT-10); return min_t(unsigned int, limit, 256*1024); } /* * Compute the number of hash buckets we need. Divide the max cachesize by * the "target" max bucket size, and round up to next power of two. */ static unsigned int nfsd_hashsize(unsigned int limit) { return roundup_pow_of_two(limit / TARGET_BUCKET_SIZE); } static u32 nfsd_cache_hash(__be32 xid) { return hash_32(be32_to_cpu(xid), maskbits); } static struct svc_cacherep * nfsd_reply_cache_alloc(struct svc_rqst *rqstp, __wsum csum) { struct svc_cacherep *rp; rp = kmem_cache_alloc(drc_slab, GFP_KERNEL); if (rp) { rp->c_state = RC_UNUSED; rp->c_type = RC_NOCACHE; RB_CLEAR_NODE(&rp->c_node); INIT_LIST_HEAD(&rp->c_lru); memset(&rp->c_key, 0, sizeof(rp->c_key)); rp->c_key.k_xid = rqstp->rq_xid; rp->c_key.k_proc = rqstp->rq_proc; rpc_copy_addr((struct sockaddr *)&rp->c_key.k_addr, svc_addr(rqstp)); rpc_set_port((struct sockaddr *)&rp->c_key.k_addr, rpc_get_port(svc_addr(rqstp))); rp->c_key.k_prot = rqstp->rq_prot; rp->c_key.k_vers = rqstp->rq_vers; rp->c_key.k_len = rqstp->rq_arg.len; rp->c_key.k_csum = csum; } return rp; } static void nfsd_reply_cache_free_locked(struct nfsd_drc_bucket *b, struct svc_cacherep *rp) { if (rp->c_type == RC_REPLBUFF && rp->c_replvec.iov_base) { drc_mem_usage -= rp->c_replvec.iov_len; kfree(rp->c_replvec.iov_base); } if (rp->c_state != RC_UNUSED) { rb_erase(&rp->c_node, &b->rb_head); list_del(&rp->c_lru); atomic_dec(&num_drc_entries); drc_mem_usage -= sizeof(*rp); } kmem_cache_free(drc_slab, rp); } static void nfsd_reply_cache_free(struct nfsd_drc_bucket *b, struct svc_cacherep *rp) { spin_lock(&b->cache_lock); nfsd_reply_cache_free_locked(b, rp); spin_unlock(&b->cache_lock); } int nfsd_reply_cache_init(void) { unsigned int hashsize; unsigned int i; int status = 0; max_drc_entries = nfsd_cache_size_limit(); atomic_set(&num_drc_entries, 0); hashsize = nfsd_hashsize(max_drc_entries); maskbits = ilog2(hashsize); status = register_shrinker(&nfsd_reply_cache_shrinker); if (status) return status; drc_slab = kmem_cache_create("nfsd_drc", sizeof(struct svc_cacherep), 0, 0, NULL); if (!drc_slab) goto out_nomem; drc_hashtbl = kcalloc(hashsize, sizeof(*drc_hashtbl), GFP_KERNEL); if (!drc_hashtbl) { drc_hashtbl = vzalloc(array_size(hashsize, sizeof(*drc_hashtbl))); if (!drc_hashtbl) goto out_nomem; } for (i = 0; i < hashsize; i++) { INIT_LIST_HEAD(&drc_hashtbl[i].lru_head); spin_lock_init(&drc_hashtbl[i].cache_lock); } drc_hashsize = hashsize; return 0; out_nomem: printk(KERN_ERR "nfsd: failed to allocate reply cache\n"); nfsd_reply_cache_shutdown(); return -ENOMEM; } void nfsd_reply_cache_shutdown(void) { struct svc_cacherep *rp; unsigned int i; unregister_shrinker(&nfsd_reply_cache_shrinker); for (i = 0; i < drc_hashsize; i++) { struct list_head *head = &drc_hashtbl[i].lru_head; while (!list_empty(head)) { rp = list_first_entry(head, struct svc_cacherep, c_lru); nfsd_reply_cache_free_locked(&drc_hashtbl[i], rp); } } kvfree(drc_hashtbl); drc_hashtbl = NULL; drc_hashsize = 0; kmem_cache_destroy(drc_slab); drc_slab = NULL; } /* * Move cache entry to end of LRU list, and queue the cleaner to run if it's * not already scheduled. */ static void lru_put_end(struct nfsd_drc_bucket *b, struct svc_cacherep *rp) { rp->c_timestamp = jiffies; list_move_tail(&rp->c_lru, &b->lru_head); } static long prune_bucket(struct nfsd_drc_bucket *b) { struct svc_cacherep *rp, *tmp; long freed = 0; list_for_each_entry_safe(rp, tmp, &b->lru_head, c_lru) { /* * Don't free entries attached to calls that are still * in-progress, but do keep scanning the list. */ if (rp->c_state == RC_INPROG) continue; if (atomic_read(&num_drc_entries) <= max_drc_entries && time_before(jiffies, rp->c_timestamp + RC_EXPIRE)) break; nfsd_reply_cache_free_locked(b, rp); freed++; } return freed; } /* * Walk the LRU list and prune off entries that are older than RC_EXPIRE. * Also prune the oldest ones when the total exceeds the max number of entries. */ static long prune_cache_entries(void) { unsigned int i; long freed = 0; for (i = 0; i < drc_hashsize; i++) { struct nfsd_drc_bucket *b = &drc_hashtbl[i]; if (list_empty(&b->lru_head)) continue; spin_lock(&b->cache_lock); freed += prune_bucket(b); spin_unlock(&b->cache_lock); } return freed; } static unsigned long nfsd_reply_cache_count(struct shrinker *shrink, struct shrink_control *sc) { return atomic_read(&num_drc_entries); } static unsigned long nfsd_reply_cache_scan(struct shrinker *shrink, struct shrink_control *sc) { return prune_cache_entries(); } /* * Walk an xdr_buf and get a CRC for at most the first RC_CSUMLEN bytes */ static __wsum nfsd_cache_csum(struct svc_rqst *rqstp) { int idx; unsigned int base; __wsum csum; struct xdr_buf *buf = &rqstp->rq_arg; const unsigned char *p = buf->head[0].iov_base; size_t csum_len = min_t(size_t, buf->head[0].iov_len + buf->page_len, RC_CSUMLEN); size_t len = min(buf->head[0].iov_len, csum_len); /* rq_arg.head first */ csum = csum_partial(p, len, 0); csum_len -= len; /* Continue into page array */ idx = buf->page_base / PAGE_SIZE; base = buf->page_base & ~PAGE_MASK; while (csum_len) { p = page_address(buf->pages[idx]) + base; len = min_t(size_t, PAGE_SIZE - base, csum_len); csum = csum_partial(p, len, csum); csum_len -= len; base = 0; ++idx; } return csum; } static int nfsd_cache_key_cmp(const struct svc_cacherep *key, const struct svc_cacherep *rp) { if (key->c_key.k_xid == rp->c_key.k_xid && key->c_key.k_csum != rp->c_key.k_csum) ++payload_misses; return memcmp(&key->c_key, &rp->c_key, sizeof(key->c_key)); } /* * Search the request hash for an entry that matches the given rqstp. * Must be called with cache_lock held. Returns the found entry or * inserts an empty key on failure. */ static struct svc_cacherep * nfsd_cache_insert(struct nfsd_drc_bucket *b, struct svc_cacherep *key) { struct svc_cacherep *rp, *ret = key; struct rb_node **p = &b->rb_head.rb_node, *parent = NULL; unsigned int entries = 0; int cmp; while (*p != NULL) { ++entries; parent = *p; rp = rb_entry(parent, struct svc_cacherep, c_node); cmp = nfsd_cache_key_cmp(key, rp); if (cmp < 0) p = &parent->rb_left; else if (cmp > 0) p = &parent->rb_right; else { ret = rp; goto out; } } rb_link_node(&key->c_node, parent, p); rb_insert_color(&key->c_node, &b->rb_head); out: /* tally hash chain length stats */ if (entries > longest_chain) { longest_chain = entries; longest_chain_cachesize = atomic_read(&num_drc_entries); } else if (entries == longest_chain) { /* prefer to keep the smallest cachesize possible here */ longest_chain_cachesize = min_t(unsigned int, longest_chain_cachesize, atomic_read(&num_drc_entries)); } lru_put_end(b, ret); return ret; } /* * Try to find an entry matching the current call in the cache. When none * is found, we try to grab the oldest expired entry off the LRU list. If * a suitable one isn't there, then drop the cache_lock and allocate a * new one, then search again in case one got inserted while this thread * didn't hold the lock. */ int nfsd_cache_lookup(struct svc_rqst *rqstp) { struct svc_cacherep *rp, *found; __be32 xid = rqstp->rq_xid; __wsum csum; u32 hash = nfsd_cache_hash(xid); struct nfsd_drc_bucket *b = &drc_hashtbl[hash]; int type = rqstp->rq_cachetype; int rtn = RC_DOIT; rqstp->rq_cacherep = NULL; if (type == RC_NOCACHE) { nfsdstats.rcnocache++; return rtn; } csum = nfsd_cache_csum(rqstp); /* * Since the common case is a cache miss followed by an insert, * preallocate an entry. */ rp = nfsd_reply_cache_alloc(rqstp, csum); if (!rp) { dprintk("nfsd: unable to allocate DRC entry!\n"); return rtn; } spin_lock(&b->cache_lock); found = nfsd_cache_insert(b, rp); if (found != rp) { nfsd_reply_cache_free_locked(NULL, rp); rp = found; goto found_entry; } nfsdstats.rcmisses++; rqstp->rq_cacherep = rp; rp->c_state = RC_INPROG; atomic_inc(&num_drc_entries); drc_mem_usage += sizeof(*rp); /* go ahead and prune the cache */ prune_bucket(b); out: spin_unlock(&b->cache_lock); return rtn; found_entry: /* We found a matching entry which is either in progress or done. */ nfsdstats.rchits++; rtn = RC_DROPIT; /* Request being processed */ if (rp->c_state == RC_INPROG) goto out; /* From the hall of fame of impractical attacks: * Is this a user who tries to snoop on the cache? */ rtn = RC_DOIT; if (!test_bit(RQ_SECURE, &rqstp->rq_flags) && rp->c_secure) goto out; /* Compose RPC reply header */ switch (rp->c_type) { case RC_NOCACHE: break; case RC_REPLSTAT: svc_putu32(&rqstp->rq_res.head[0], rp->c_replstat); rtn = RC_REPLY; break; case RC_REPLBUFF: if (!nfsd_cache_append(rqstp, &rp->c_replvec)) goto out; /* should not happen */ rtn = RC_REPLY; break; default: printk(KERN_WARNING "nfsd: bad repcache type %d\n", rp->c_type); nfsd_reply_cache_free_locked(b, rp); } goto out; } /* * Update a cache entry. This is called from nfsd_dispatch when * the procedure has been executed and the complete reply is in * rqstp->rq_res. * * We're copying around data here rather than swapping buffers because * the toplevel loop requires max-sized buffers, which would be a waste * of memory for a cache with a max reply size of 100 bytes (diropokres). * * If we should start to use different types of cache entries tailored * specifically for attrstat and fh's, we may save even more space. * * Also note that a cachetype of RC_NOCACHE can legally be passed when * nfsd failed to encode a reply that otherwise would have been cached. * In this case, nfsd_cache_update is called with statp == NULL. */ void nfsd_cache_update(struct svc_rqst *rqstp, int cachetype, __be32 *statp) { struct svc_cacherep *rp = rqstp->rq_cacherep; struct kvec *resv = &rqstp->rq_res.head[0], *cachv; u32 hash; struct nfsd_drc_bucket *b; int len; size_t bufsize = 0; if (!rp) return; hash = nfsd_cache_hash(rp->c_key.k_xid); b = &drc_hashtbl[hash]; len = resv->iov_len - ((char*)statp - (char*)resv->iov_base); len >>= 2; /* Don't cache excessive amounts of data and XDR failures */ if (!statp || len > (256 >> 2)) { nfsd_reply_cache_free(b, rp); return; } switch (cachetype) { case RC_REPLSTAT: if (len != 1) printk("nfsd: RC_REPLSTAT/reply len %d!\n",len); rp->c_replstat = *statp; break; case RC_REPLBUFF: cachv = &rp->c_replvec; bufsize = len << 2; cachv->iov_base = kmalloc(bufsize, GFP_KERNEL); if (!cachv->iov_base) { nfsd_reply_cache_free(b, rp); return; } cachv->iov_len = bufsize; memcpy(cachv->iov_base, statp, bufsize); break; case RC_NOCACHE: nfsd_reply_cache_free(b, rp); return; } spin_lock(&b->cache_lock); drc_mem_usage += bufsize; lru_put_end(b, rp); rp->c_secure = test_bit(RQ_SECURE, &rqstp->rq_flags); rp->c_type = cachetype; rp->c_state = RC_DONE; spin_unlock(&b->cache_lock); return; } /* * Copy cached reply to current reply buffer. Should always fit. * FIXME as reply is in a page, we should just attach the page, and * keep a refcount.... */ static int nfsd_cache_append(struct svc_rqst *rqstp, struct kvec *data) { struct kvec *vec = &rqstp->rq_res.head[0]; if (vec->iov_len + data->iov_len > PAGE_SIZE) { printk(KERN_WARNING "nfsd: cached reply too large (%zd).\n", data->iov_len); return 0; } memcpy((char*)vec->iov_base + vec->iov_len, data->iov_base, data->iov_len); vec->iov_len += data->iov_len; return 1; } /* * Note that fields may be added, removed or reordered in the future. Programs * scraping this file for info should test the labels to ensure they're * getting the correct field. */ static int nfsd_reply_cache_stats_show(struct seq_file *m, void *v) { seq_printf(m, "max entries: %u\n", max_drc_entries); seq_printf(m, "num entries: %u\n", atomic_read(&num_drc_entries)); seq_printf(m, "hash buckets: %u\n", 1 << maskbits); seq_printf(m, "mem usage: %u\n", drc_mem_usage); seq_printf(m, "cache hits: %u\n", nfsdstats.rchits); seq_printf(m, "cache misses: %u\n", nfsdstats.rcmisses); seq_printf(m, "not cached: %u\n", nfsdstats.rcnocache); seq_printf(m, "payload misses: %u\n", payload_misses); seq_printf(m, "longest chain len: %u\n", longest_chain); seq_printf(m, "cachesize at longest: %u\n", longest_chain_cachesize); return 0; } int nfsd_reply_cache_stats_open(struct inode *inode, struct file *file) { return single_open(file, nfsd_reply_cache_stats_show, NULL); }