1f6d334e0SBrad Fitzpatrick/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
256b8339eSSteven Grimm#include "memcached.h"
3c6975ef4SPaul Lindner#include <errno.h>
460d70942SAnatoly Vorobey#include <stdlib.h>
560d70942SAnatoly Vorobey#include <stdio.h>
660d70942SAnatoly Vorobey#include <string.h>
71b533267SBrad Fitzpatrick#include <time.h>
843202f2fSBrad Fitzpatrick#include <assert.h>
96a48c213SManik Taneja#include "log.h"
1086969ea4SBrad Fitzpatrick
1177dde9f9SPaul Lindner/* Forward Declarations */
1277dde9f9SPaul Lindnerstatic void item_link_q(item *it);
1377dde9f9SPaul Lindnerstatic void item_unlink_q(item *it);
1477dde9f9SPaul Lindner
15217dcce0SSteven Grimm/*
16217dcce0SSteven Grimm * We only reposition items in the LRU queue if they haven't been repositioned
17217dcce0SSteven Grimm * in this many seconds. That saves us from churning on frequently-accessed
18217dcce0SSteven Grimm * items.
19217dcce0SSteven Grimm */
20217dcce0SSteven Grimm#define ITEM_UPDATE_INTERVAL 60
2186969ea4SBrad Fitzpatrick
22c9607c6dSBrad Fitzpatrick#define LARGEST_ID 255
235e0bb476Sdormandotypedef struct {
245e0bb476Sdormando    unsigned int evicted;
257a2dd7a2Sdormando    rel_time_t evicted_time;
265e0bb476Sdormando    unsigned int outofmemory;
274ad6da60Sdormando    unsigned int tailrepairs;
285e0bb476Sdormando} itemstats_t;
295e0bb476Sdormando
3060d70942SAnatoly Vorobeystatic item *heads[LARGEST_ID];
3160d70942SAnatoly Vorobeystatic item *tails[LARGEST_ID];
325e0bb476Sdormandostatic itemstats_t itemstats[LARGEST_ID];
3377dde9f9SPaul Lindnerstatic unsigned int sizes[LARGEST_ID];
3486969ea4SBrad Fitzpatrick
3560d70942SAnatoly Vorobeyvoid item_init(void) {
3660d70942SAnatoly Vorobey    int i;
375e0bb476Sdormando    memset(itemstats, 0, sizeof(itemstats_t) * LARGEST_ID);
3878955139STim Yardley    for(i = 0; i < LARGEST_ID; i++) {
3978955139STim Yardley        heads[i] = NULL;
4078955139STim Yardley        tails[i] = NULL;
4178955139STim Yardley        sizes[i] = 0;
4260d70942SAnatoly Vorobey    }
4360d70942SAnatoly Vorobey}
4486969ea4SBrad Fitzpatrick
4553180103STrond Norbyevoid item_stats_reset(void) {
467d4ff237STrond Norbye    cb_mutex_enter(&cache_lock);
4753180103STrond Norbye    memset(itemstats, 0, sizeof(itemstats_t) * LARGEST_ID);
487d4ff237STrond Norbye    cb_mutex_exit(&cache_lock);
4953180103STrond Norbye}
5053180103STrond Norbye
5153180103STrond Norbye
52e4a45965SDustin Sallings/* Get the next CAS id for a new item. */
53df1b7e42STrond Norbyeuint64_t get_cas_id(void) {
54579466f2Sdormando    static uint64_t cas_id = 0;
55e4a45965SDustin Sallings    return ++cas_id;
56e4a45965SDustin Sallings}
57e4a45965SDustin Sallings
5856b8339eSSteven Grimm/* Enable this for reference-count debugging. */
5956b8339eSSteven Grimm#if 0
6056b8339eSSteven Grimm# define DEBUG_REFCNT(it,op) \
616a48c213SManik Taneja                moxi_log_write("item %x refcnt(%c) %d %c%c%c\n", \
6256b8339eSSteven Grimm                        it, op, it->refcount, \
6356b8339eSSteven Grimm                        (it->it_flags & ITEM_LINKED) ? 'L' : ' ', \
645da8dbabSTrond Norbye                        (it->it_flags & ITEM_SLABBED) ? 'S' : ' ')
6556b8339eSSteven Grimm#else
666fcace5dSTrond Norbye# define DEBUG_REFCNT(it,op) do {} while(0)
6756b8339eSSteven Grimm#endif
6886969ea4SBrad Fitzpatrick
6944ef96eeSPaul Lindner/**
70c9607c6dSBrad Fitzpatrick * Generates the variable-sized part of the header for an object.
71c9607c6dSBrad Fitzpatrick *
72b80ab7cfSPaul Lindner * key     - The key
73217dcce0SSteven Grimm * nkey    - The length of the key
74217dcce0SSteven Grimm * flags   - key flags
75217dcce0SSteven Grimm * nbytes  - Number of bytes to hold value and addition CRLF terminator
76c9607c6dSBrad Fitzpatrick * suffix  - Buffer for the "VALUE" line suffix (flags, size).
77c9607c6dSBrad Fitzpatrick * nsuffix - The length of the suffix is stored here.
78c9607c6dSBrad Fitzpatrick *
79c9607c6dSBrad Fitzpatrick * Returns the total size of the header.
80c9607c6dSBrad Fitzpatrick */
8110862f60SPaul Lindnerstatic size_t item_make_header(const uint8_t nkey, const int flags, const int nbytes,
8277dde9f9SPaul Lindner                     char *suffix, uint8_t *nsuffix) {
8377dde9f9SPaul Lindner    /* suffix is defined at 40 chars elsewhere.. */
8477dde9f9SPaul Lindner    *nsuffix = (uint8_t) snprintf(suffix, 40, " %d %d\r\n", flags, nbytes - 2);
85217dcce0SSteven Grimm    return sizeof(item) + nkey + *nsuffix + nbytes;
86c9607c6dSBrad Fitzpatrick}
87b80ab7cfSPaul Lindner
8877dde9f9SPaul Lindner/*@null@*/
8956b8339eSSteven Grimmitem *do_item_alloc(char *key, const size_t nkey, const int flags, const rel_time_t exptime, const int nbytes) {
9077dde9f9SPaul Lindner    uint8_t nsuffix;
91c9607c6dSBrad Fitzpatrick    char suffix[40];
9278955139STim Yardley    size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
93eda68b70STrond Norbye    if (settings.use_cas) {
94eda68b70STrond Norbye        ntotal += sizeof(uint64_t);
95eda68b70STrond Norbye    }
9686969ea4SBrad Fitzpatrick
97a995404dSSteve Yen#ifdef MOXI_ITEM_MALLOC
98b33ce538SSteve Yen    item *itx = malloc(ntotal);
99b33ce538SSteve Yen    if (itx != NULL) {
100b33ce538SSteve Yen        itx->refcount = 1;
101b33ce538SSteve Yen        itx->slabs_clsid = 0;
102b33ce538SSteve Yen        itx->next = 0;
103b33ce538SSteve Yen        itx->prev = 0;
104b33ce538SSteve Yen        itx->h_next = 0;
105b33ce538SSteve Yen        itx->it_flags = settings.use_cas ? ITEM_CAS : 0;
106b33ce538SSteve Yen        itx->nkey = nkey;
107b33ce538SSteve Yen        itx->nbytes = nbytes;
108b33ce538SSteve Yen        memcpy(ITEM_key(itx), key, nkey);
109b33ce538SSteve Yen        itx->exptime = exptime;
110b33ce538SSteve Yen        memcpy(ITEM_suffix(itx), suffix, (size_t)nsuffix);
111b33ce538SSteve Yen        itx->nsuffix = nsuffix;
112b33ce538SSteve Yen    }
113b33ce538SSteve Yen
114b33ce538SSteve Yen    return itx;
115a995404dSSteve Yen#else
11678955139STim Yardley    unsigned int id = slabs_clsid(ntotal);
11760d70942SAnatoly Vorobey    if (id == 0)
11860d70942SAnatoly Vorobey        return 0;
11986969ea4SBrad Fitzpatrick
120d3807d06STrond Norbye    /* do a quick check if we have any expired items in the tail.. */
121d3807d06STrond Norbye    int tries = 50;
12248df3595SSteve Yen    item *it = NULL;
123d3807d06STrond Norbye    item *search;
124d3807d06STrond Norbye
125d3807d06STrond Norbye    for (search = tails[id];
126d3807d06STrond Norbye         tries > 0 && search != NULL;
127d3807d06STrond Norbye         tries--, search=search->prev) {
128d3807d06STrond Norbye        if (search->refcount == 0 &&
129d3807d06STrond Norbye            (search->exptime != 0 && search->exptime < current_time)) {
130d3807d06STrond Norbye            it = search;
131d3807d06STrond Norbye            /* I don't want to actually free the object, just steal
132d3807d06STrond Norbye             * the item to avoid to grab the slab mutex twice ;-)
133d3807d06STrond Norbye             */
134d3807d06STrond Norbye            it->refcount = 1;
135d3807d06STrond Norbye            do_item_unlink(it);
136d3807d06STrond Norbye            /* Initialize the item block: */
137d3807d06STrond Norbye            it->slabs_clsid = 0;
138d3807d06STrond Norbye            it->refcount = 0;
139d3807d06STrond Norbye            break;
140d3807d06STrond Norbye        }
141d3807d06STrond Norbye    }
142d3807d06STrond Norbye
143d3807d06STrond Norbye    if (it == NULL && (it = slabs_alloc(ntotal, id)) == NULL) {
144d3807d06STrond Norbye        /*
145d3807d06STrond Norbye        ** Could not find an expired item at the tail, and memory allocation
146d3807d06STrond Norbye        ** failed. Try to evict some items!
147d3807d06STrond Norbye        */
148d3807d06STrond Norbye        tries = 50;
14986969ea4SBrad Fitzpatrick
150841811e9SJason Titus        /* If requested to not push old items out of cache when memory runs out,
151841811e9SJason Titus         * we're out of luck at this point...
152841811e9SJason Titus         */
15386969ea4SBrad Fitzpatrick
1545e0bb476Sdormando        if (settings.evict_to_free == 0) {
1555e0bb476Sdormando            itemstats[id].outofmemory++;
1565e0bb476Sdormando            return NULL;
1575e0bb476Sdormando        }
15886969ea4SBrad Fitzpatrick
159b80ab7cfSPaul Lindner        /*
160b80ab7cfSPaul Lindner         * try to get one off the right LRU
16160d70942SAnatoly Vorobey         * don't necessariuly unlink the tail because it may be locked: refcount>0
16260d70942SAnatoly Vorobey         * search up from tail an item with refcount==0 and unlink it; give up after 50
16360d70942SAnatoly Vorobey         * tries
16460d70942SAnatoly Vorobey         */
16586969ea4SBrad Fitzpatrick
1665e0bb476Sdormando        if (tails[id] == 0) {
1675e0bb476Sdormando            itemstats[id].outofmemory++;
1685e0bb476Sdormando            return NULL;
1695e0bb476Sdormando        }
17086969ea4SBrad Fitzpatrick
171eca55c9aSPaul Lindner        for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
17278955139STim Yardley            if (search->refcount == 0) {
1735e0bb476Sdormando                if (search->exptime == 0 || search->exptime > current_time) {
1745e0bb476Sdormando                    itemstats[id].evicted++;
1757a2dd7a2Sdormando                    itemstats[id].evicted_time = current_time - search->time;
1765e0bb476Sdormando                    STATS_LOCK();
1775e0bb476Sdormando                    stats.evictions++;
1785e0bb476Sdormando                    STATS_UNLOCK();
17956b8339eSSteven Grimm                }
18056b8339eSSteven Grimm                do_item_unlink(search);
18160d70942SAnatoly Vorobey                break;
18260d70942SAnatoly Vorobey            }
18360d70942SAnatoly Vorobey        }
18401fa48f0Sdormando        it = slabs_alloc(ntotal, id);
1855e0bb476Sdormando        if (it == 0) {
1865e0bb476Sdormando            itemstats[id].outofmemory++;
1874ad6da60Sdormando            /* Last ditch effort. There is a very rare bug which causes
1884ad6da60Sdormando             * refcount leaks. We've fixed most of them, but it still happens,
1894ad6da60Sdormando             * and it may happen in the future.
1904ad6da60Sdormando             * We can reasonably assume no item can stay locked for more than
1914ad6da60Sdormando             * three hours, so if we find one in the tail which is that old,
1924ad6da60Sdormando             * free it anyway.
1934ad6da60Sdormando             */
1944ad6da60Sdormando            tries = 50;
1954ad6da60Sdormando            for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
196b8d997e5SDustin Sallings                if (search->refcount != 0 && search->time + TAIL_REPAIR_TIME < current_time) {
1974ad6da60Sdormando                    itemstats[id].tailrepairs++;
1984ad6da60Sdormando                    search->refcount = 0;
1994ad6da60Sdormando                    do_item_unlink(search);
2004ad6da60Sdormando                    break;
2014ad6da60Sdormando                }
2024ad6da60Sdormando            }
2034ad6da60Sdormando            it = slabs_alloc(ntotal, id);
2044ad6da60Sdormando            if (it == 0) {
2054ad6da60Sdormando                return NULL;
2064ad6da60Sdormando            }
2075e0bb476Sdormando        }
20860d70942SAnatoly Vorobey    }
20986969ea4SBrad Fitzpatrick
210c08383afSBrad Fitzpatrick    assert(it->slabs_clsid == 0);
21186969ea4SBrad Fitzpatrick
21260d70942SAnatoly Vorobey    it->slabs_clsid = id;
21386969ea4SBrad Fitzpatrick
2148cb3381aSBrad Fitzpatrick    assert(it != heads[it->slabs_clsid]);
21586969ea4SBrad Fitzpatrick
216f6d334e0SBrad Fitzpatrick    it->next = it->prev = it->h_next = 0;
21756b8339eSSteven Grimm    it->refcount = 1;     /* the caller will have a reference */
21856b8339eSSteven Grimm    DEBUG_REFCNT(it, '*');
219eda68b70STrond Norbye    it->it_flags = settings.use_cas ? ITEM_CAS : 0;
220217dcce0SSteven Grimm    it->nkey = nkey;
22160d70942SAnatoly Vorobey    it->nbytes = nbytes;
22241aa0a55STrond Norbye    memcpy(ITEM_key(it), key, nkey);
223f6d334e0SBrad Fitzpatrick    it->exptime = exptime;
22478955139STim Yardley    memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);
225c9607c6dSBrad Fitzpatrick    it->nsuffix = nsuffix;
22660d70942SAnatoly Vorobey    return it;
227a995404dSSteve Yen#endif
22860d70942SAnatoly Vorobey}
22986969ea4SBrad Fitzpatrick
23060d70942SAnatoly Vorobeyvoid item_free(item *it) {
231a995404dSSteve Yen#ifdef MOXI_ITEM_MALLOC
232b33ce538SSteve Yen    assert(it->refcount > 0);
233b33ce538SSteve Yen    it->refcount--;
234b33ce538SSteve Yen    if (it->refcount == 0) {
235b33ce538SSteve Yen        free(it);
236b33ce538SSteve Yen    }
237a995404dSSteve Yen#else
23877dde9f9SPaul Lindner    size_t ntotal = ITEM_ntotal(it);
2398d3ac826Sdormando    unsigned int clsid;
24043202f2fSBrad Fitzpatrick    assert((it->it_flags & ITEM_LINKED) == 0);
2411baa8961SBrad Fitzpatrick    assert(it != heads[it->slabs_clsid]);
2421baa8961SBrad Fitzpatrick    assert(it != tails[it->slabs_clsid]);
2431ea89bd5SBrad Fitzpatrick    assert(it->refcount == 0);
24486969ea4SBrad Fitzpatrick
245b7b9d5f4SBrad Fitzpatrick    /* so slab size changer can tell later if item is already free or not */
2468d3ac826Sdormando    clsid = it->slabs_clsid;
247b7b9d5f4SBrad Fitzpatrick    it->slabs_clsid = 0;
24854326f42SBrad Fitzpatrick    it->it_flags |= ITEM_SLABBED;
24956b8339eSSteven Grimm    DEBUG_REFCNT(it, 'F');
2508d3ac826Sdormando    slabs_free(it, ntotal, clsid);
251a995404dSSteve Yen#endif
25260d70942SAnatoly Vorobey}
25386969ea4SBrad Fitzpatrick
25444ef96eeSPaul Lindner/**
255c9607c6dSBrad Fitzpatrick * Returns true if an item will fit in the cache (its size does not exceed
256c9607c6dSBrad Fitzpatrick * the maximum for a cache entry.)
257c9607c6dSBrad Fitzpatrick */
25810862f60SPaul Lindnerbool item_size_ok(const size_t nkey, const int flags, const int nbytes) {
259c9607c6dSBrad Fitzpatrick    char prefix[40];
26077dde9f9SPaul Lindner    uint8_t nsuffix;
26186969ea4SBrad Fitzpatrick
26210862f60SPaul Lindner    return slabs_clsid(item_make_header(nkey + 1, flags, nbytes,
263217dcce0SSteven Grimm                                        prefix, &nsuffix)) != 0;
264c9607c6dSBrad Fitzpatrick}
26586969ea4SBrad Fitzpatrick
26677dde9f9SPaul Lindnerstatic void item_link_q(item *it) { /* item is the new head */
267e1ae2ef8SAliaksey Kandratsenka    (void)it;
26817f02511SSteve Yen#ifndef MOXI_ITEM_MALLOC
26960d70942SAnatoly Vorobey    item **head, **tail;
27055dfb168SBrad Fitzpatrick    /* always true, warns: assert(it->slabs_clsid <= LARGEST_ID); */
27154326f42SBrad Fitzpatrick    assert((it->it_flags & ITEM_SLABBED) == 0);
27286969ea4SBrad Fitzpatrick
27360d70942SAnatoly Vorobey    head = &heads[it->slabs_clsid];
27460d70942SAnatoly Vorobey    tail = &tails[it->slabs_clsid];
27543202f2fSBrad Fitzpatrick    assert(it != *head);
27643202f2fSBrad Fitzpatrick    assert((*head && *tail) || (*head == 0 && *tail == 0));
27760d70942SAnatoly Vorobey    it->prev = 0;
27860d70942SAnatoly Vorobey    it->next = *head;
27960d70942SAnatoly Vorobey    if (it->next) it->next->prev = it;
28060d70942SAnatoly Vorobey    *head = it;
2816d74e134SBrad Fitzpatrick    if (*tail == 0) *tail = it;
28260d70942SAnatoly Vorobey    sizes[it->slabs_clsid]++;
28360d70942SAnatoly Vorobey    return;
28417f02511SSteve Yen#endif
28560d70942SAnatoly Vorobey}
28686969ea4SBrad Fitzpatrick
28777dde9f9SPaul Lindnerstatic void item_unlink_q(item *it) {
288e1ae2ef8SAliaksey Kandratsenka    (void)it;
28917f02511SSteve Yen#ifndef MOXI_ITEM_MALLOC
29060d70942SAnatoly Vorobey    item **head, **tail;
29155dfb168SBrad Fitzpatrick    /* always true, warns: assert(it->slabs_clsid <= LARGEST_ID); */
29260d70942SAnatoly Vorobey    head = &heads[it->slabs_clsid];
29360d70942SAnatoly Vorobey    tail = &tails[it->slabs_clsid];
29486969ea4SBrad Fitzpatrick
295c3b1a8c9SBrad Fitzpatrick    if (*head == it) {
296c3b1a8c9SBrad Fitzpatrick        assert(it->prev == 0);
297c3b1a8c9SBrad Fitzpatrick        *head = it->next;
298c3b1a8c9SBrad Fitzpatrick    }
299c3b1a8c9SBrad Fitzpatrick    if (*tail == it) {
300c3b1a8c9SBrad Fitzpatrick        assert(it->next == 0);
301c3b1a8c9SBrad Fitzpatrick        *tail = it->prev;
302c3b1a8c9SBrad Fitzpatrick    }
303c3b1a8c9SBrad Fitzpatrick    assert(it->next != it);
304c3b1a8c9SBrad Fitzpatrick    assert(it->prev != it);
30586969ea4SBrad Fitzpatrick
30660d70942SAnatoly Vorobey    if (it->next) it->next->prev = it->prev;
30760d70942SAnatoly Vorobey    if (it->prev) it->prev->next = it->next;
30860d70942SAnatoly Vorobey    sizes[it->slabs_clsid]--;
30960d70942SAnatoly Vorobey    return;
31017f02511SSteve Yen#endif
31160d70942SAnatoly Vorobey}
31286969ea4SBrad Fitzpatrick
31356b8339eSSteven Grimmint do_item_link(item *it) {
31480ec0955STrond Norbye    MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes);
31554326f42SBrad Fitzpatrick    assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
31695ddc95fSSteven Grimm    assert(it->nbytes < (1024 * 1024));  /* 1MB max size */
31760d70942SAnatoly Vorobey    it->it_flags |= ITEM_LINKED;
318c9607c6dSBrad Fitzpatrick    it->time = current_time;
319217dcce0SSteven Grimm    assoc_insert(it);
32086969ea4SBrad Fitzpatrick
32117f02511SSteve Yen#ifdef MOXI_ITEM_MALLOC
32217f02511SSteve Yen    it->refcount++;
32317f02511SSteve Yen#endif
32417f02511SSteve Yen
32556b8339eSSteven Grimm    STATS_LOCK();
326f6d334e0SBrad Fitzpatrick    stats.curr_bytes += ITEM_ntotal(it);
32760d70942SAnatoly Vorobey    stats.curr_items += 1;
32860d70942SAnatoly Vorobey    stats.total_items += 1;
32956b8339eSSteven Grimm    STATS_UNLOCK();
33086969ea4SBrad Fitzpatrick
331c2cdee22SDustin Sallings    /* Allocate a new CAS ID on link. */
332eda68b70STrond Norbye    ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0);
333c2cdee22SDustin Sallings
33460d70942SAnatoly Vorobey    item_link_q(it);
33586969ea4SBrad Fitzpatrick
33660d70942SAnatoly Vorobey    return 1;
33760d70942SAnatoly Vorobey}
33886969ea4SBrad Fitzpatrick
33956b8339eSSteven Grimmvoid do_item_unlink(item *it) {
34080ec0955STrond Norbye    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);
34177dde9f9SPaul Lindner    if ((it->it_flags & ITEM_LINKED) != 0) {
342fe6d2061SBrad Fitzpatrick        it->it_flags &= ~ITEM_LINKED;
34356b8339eSSteven Grimm        STATS_LOCK();
344fe6d2061SBrad Fitzpatrick        stats.curr_bytes -= ITEM_ntotal(it);
345fe6d2061SBrad Fitzpatrick        stats.curr_items -= 1;
34656b8339eSSteven Grimm        STATS_UNLOCK();
347217dcce0SSteven Grimm        assoc_delete(ITEM_key(it), it->nkey);
348fe6d2061SBrad Fitzpatrick        item_unlink_q(it);
34917f02511SSteve Yen
35017f02511SSteve Yen#ifndef MOXI_ITEM_MALLOC
35156b8339eSSteven Grimm        if (it->refcount == 0) item_free(it);
35217f02511SSteve Yen#endif
353fe6d2061SBrad Fitzpatrick    }
35460d70942SAnatoly Vorobey}
35586969ea4SBrad Fitzpatrick
35656b8339eSSteven Grimmvoid do_item_remove(item *it) {
357a995404dSSteve Yen#ifdef MOXI_ITEM_MALLOC
358b33ce538SSteve Yen    item_free(it);
359a995404dSSteve Yen#else
36080ec0955STrond Norbye    MEMCACHED_ITEM_REMOVE(ITEM_key(it), it->nkey, it->nbytes);
36154326f42SBrad Fitzpatrick    assert((it->it_flags & ITEM_SLABBED) == 0);
36256b8339eSSteven Grimm    if (it->refcount != 0) {
36356b8339eSSteven Grimm        it->refcount--;
36456b8339eSSteven Grimm        DEBUG_REFCNT(it, '-');
36556b8339eSSteven Grimm    }
36660d70942SAnatoly Vorobey    if (it->refcount == 0 && (it->it_flags & ITEM_LINKED) == 0) {
36760d70942SAnatoly Vorobey        item_free(it);
36860d70942SAnatoly Vorobey    }
369a995404dSSteve Yen#endif
37060d70942SAnatoly Vorobey}
37186969ea4SBrad Fitzpatrick
37256b8339eSSteven Grimmvoid do_item_update(item *it) {
37380ec0955STrond Norbye    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
374217dcce0SSteven Grimm    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
375217dcce0SSteven Grimm        assert((it->it_flags & ITEM_SLABBED) == 0);
37686969ea4SBrad Fitzpatrick
3779759cca7STomash Brechko        if ((it->it_flags & ITEM_LINKED) != 0) {
37856b8339eSSteven Grimm            item_unlink_q(it);
37956b8339eSSteven Grimm            it->time = current_time;
38056b8339eSSteven Grimm            item_link_q(it);
38156b8339eSSteven Grimm        }
382217dcce0SSteven Grimm    }
38360d70942SAnatoly Vorobey}
38486969ea4SBrad Fitzpatrick
38556b8339eSSteven Grimmint do_item_replace(item *it, item *new_it) {
38680ec0955STrond Norbye    MEMCACHED_ITEM_REPLACE(ITEM_key(it), it->nkey, it->nbytes,
38780ec0955STrond Norbye                           ITEM_key(new_it), new_it->nkey, new_it->nbytes);
38854326f42SBrad Fitzpatrick    assert((it->it_flags & ITEM_SLABBED) == 0);
38986969ea4SBrad Fitzpatrick
39056b8339eSSteven Grimm    do_item_unlink(it);
39156b8339eSSteven Grimm    return do_item_link(new_it);
39260d70942SAnatoly Vorobey}
39386969ea4SBrad Fitzpatrick
39477dde9f9SPaul Lindner/*@null@*/
395e1ae2ef8SAliaksey Kandratsenkachar *do_item_cachedump(const unsigned int clsid, const unsigned int limit, unsigned int *bytes) {
39644ef96eeSPaul Lindner    unsigned int memlimit = 2 * 1024 * 1024;   /* 2MB max response size */
39760d70942SAnatoly Vorobey    char *buffer;
39877dde9f9SPaul Lindner    unsigned int bufcurr;
39960d70942SAnatoly Vorobey    item *it;
40044ef96eeSPaul Lindner    unsigned int len;
40144ef96eeSPaul Lindner    unsigned int shown = 0;
402ecdb0114SDustin Sallings    char key_temp[KEY_MAX_LENGTH + 1];
4038f5960e0SBrad Fitzpatrick    char temp[512];
40486969ea4SBrad Fitzpatrick
405e1ae2ef8SAliaksey Kandratsenka    if (clsid > LARGEST_ID) return NULL;
406e1ae2ef8SAliaksey Kandratsenka    it = heads[clsid];
40786969ea4SBrad Fitzpatrick
40877dde9f9SPaul Lindner    buffer = malloc((size_t)memlimit);
40977dde9f9SPaul Lindner    if (buffer == 0) return NULL;
41060d70942SAnatoly Vorobey    bufcurr = 0;
41186969ea4SBrad Fitzpatrick
41278955139STim Yardley    while (it != NULL && (limit == 0 || shown < limit)) {
413ecdb0114SDustin Sallings        assert(it->nkey <= KEY_MAX_LENGTH);
414ecdb0114SDustin Sallings        /* Copy the key since it may not be null-terminated in the struct */
415bd2f3ab2SDustin Sallings        strncpy(key_temp, ITEM_key(it), it->nkey);
416bd2f3ab2SDustin Sallings        key_temp[it->nkey] = 0x00; /* terminate */
4177dcfcedcSDustin Sallings        len = snprintf(temp, sizeof(temp), "ITEM %s [%d b; %lu s]\r\n",
418ecdb0114SDustin Sallings                       key_temp, it->nbytes - 2,
4191fdfb7e9STrond Norbye                       (unsigned long)it->exptime + process_started);
420d5d9ff0dSAndrei Nigmatulin        if (bufcurr + len + 6 > memlimit)  /* 6 is END\r\n\0 */
42160d70942SAnatoly Vorobey            break;
42248eb8857SDustin Sallings        memcpy(buffer + bufcurr, temp, len);
42378955139STim Yardley        bufcurr += len;
42460d70942SAnatoly Vorobey        shown++;
42560d70942SAnatoly Vorobey        it = it->next;
42660d70942SAnatoly Vorobey    }
42786969ea4SBrad Fitzpatrick
428c47ee897SPaul Lindner    memcpy(buffer + bufcurr, "END\r\n", 6);
42978955139STim Yardley    bufcurr += 5;
43086969ea4SBrad Fitzpatrick
43160d70942SAnatoly Vorobey    *bytes = bufcurr;
43260d70942SAnatoly Vorobey    return buffer;
43360d70942SAnatoly Vorobey}
43486969ea4SBrad Fitzpatrick
43517df5c0eSTrond Norbyevoid do_item_stats(ADD_STAT add_stats, void *c) {
43617df5c0eSTrond Norbye    int i;
43778955139STim Yardley    for (i = 0; i < LARGEST_ID; i++) {
4380b211d45SSteven Grimm        if (tails[i] != NULL) {
439b89f7c7bSDustin Sallings            const char *fmt = "items:%d:%s";
44048eb8857SDustin Sallings            char key_str[STAT_KEY_LEN];
44148eb8857SDustin Sallings            char val_str[STAT_VAL_LEN];
442b89f7c7bSDustin Sallings            int klen = 0, vlen = 0;
443b89f7c7bSDustin Sallings
444b89f7c7bSDustin Sallings            APPEND_NUM_FMT_STAT(fmt, i, "number", "%u", sizes[i]);
445b89f7c7bSDustin Sallings            APPEND_NUM_FMT_STAT(fmt, i, "age", "%u", tails[i]->time);
446b89f7c7bSDustin Sallings            APPEND_NUM_FMT_STAT(fmt, i, "evicted",
447b89f7c7bSDustin Sallings                                "%u", itemstats[i].evicted);
448b89f7c7bSDustin Sallings            APPEND_NUM_FMT_STAT(fmt, i, "evicted_time",
449b89f7c7bSDustin Sallings                                "%u", itemstats[i].evicted_time);
450b89f7c7bSDustin Sallings            APPEND_NUM_FMT_STAT(fmt, i, "outofmemory",
451b89f7c7bSDustin Sallings                                "%u", itemstats[i].outofmemory);
4524ad6da60Sdormando            APPEND_NUM_FMT_STAT(fmt, i, "tailrepairs",
4534ad6da60Sdormando                                "%u", itemstats[i].tailrepairs);;
4540b211d45SSteven Grimm        }
45560d70942SAnatoly Vorobey    }
456ee6df65aSSteven Grimm
45748f45982SToru Maesaka    /* getting here means both ascii and binary terminators fit */
45817df5c0eSTrond Norbye    add_stats(NULL, 0, NULL, 0, c);
45960d70942SAnatoly Vorobey}
46086969ea4SBrad Fitzpatrick
46144ef96eeSPaul Lindner/** dumps out a list of objects of each size, with granularity of 32 bytes */
46277dde9f9SPaul Lindner/*@null@*/
46317df5c0eSTrond Norbyevoid do_item_stats_sizes(ADD_STAT add_stats, void *c) {
464e2df488bSToru Maesaka
465f8770bf2SDustin Sallings    /* max 1MB object, divided into 32 bytes size buckets */
466f8770bf2SDustin Sallings    const int num_buckets = 32768;
46717df5c0eSTrond Norbye    unsigned int *histogram = calloc(num_buckets, sizeof(int));
46817df5c0eSTrond Norbye
46917df5c0eSTrond Norbye    if (histogram != NULL) {
47017df5c0eSTrond Norbye        int i;
47117df5c0eSTrond Norbye
47217df5c0eSTrond Norbye        /* build the histogram */
47317df5c0eSTrond Norbye        for (i = 0; i < LARGEST_ID; i++) {
47417df5c0eSTrond Norbye            item *iter = heads[i];
47517df5c0eSTrond Norbye            while (iter) {
47617df5c0eSTrond Norbye                int ntotal = ITEM_ntotal(iter);
47717df5c0eSTrond Norbye                int bucket = ntotal / 32;
47817df5c0eSTrond Norbye                if ((ntotal % 32) != 0) bucket++;
47917df5c0eSTrond Norbye                if (bucket < num_buckets) histogram[bucket]++;
48017df5c0eSTrond Norbye                iter = iter->next;
48117df5c0eSTrond Norbye            }
4826d74e134SBrad Fitzpatrick        }
48386969ea4SBrad Fitzpatrick
48417df5c0eSTrond Norbye        /* write the buffer */
48517df5c0eSTrond Norbye        for (i = 0; i < num_buckets; i++) {
48617df5c0eSTrond Norbye            if (histogram[i] != 0) {
48717df5c0eSTrond Norbye                char key[8];
48817df5c0eSTrond Norbye                int klen = 0;
48948eb8857SDustin Sallings                klen = snprintf(key, sizeof(key), "%d", i * 32);
49072ed961aSSteve Yen                assert(klen < (int) sizeof(key));
49117df5c0eSTrond Norbye                APPEND_STAT(key, "%u", histogram[i]);
49217df5c0eSTrond Norbye            }
4936d74e134SBrad Fitzpatrick        }
49417df5c0eSTrond Norbye        free(histogram);
4956d74e134SBrad Fitzpatrick    }
49617df5c0eSTrond Norbye    add_stats(NULL, 0, NULL, 0, c);
4978bdbe4a3SBrad Fitzpatrick}
498c5944dc2SSteven Grimm
4995da8dbabSTrond Norbye/** wrapper around assoc_find which does the lazy expiration logic */
5005da8dbabSTrond Norbyeitem *do_item_get(const char *key, const size_t nkey) {
50156b8339eSSteven Grimm    item *it = assoc_find(key, nkey);
50291adade7Sdormando    int was_found = 0;
50391adade7Sdormando
50491adade7Sdormando    if (settings.verbose > 2) {
50591adade7Sdormando        if (it == NULL) {
5066a48c213SManik Taneja            moxi_log_write("> NOT FOUND %s", key);
50791adade7Sdormando        } else {
5086a48c213SManik Taneja            moxi_log_write("> FOUND KEY %s", ITEM_key(it));
50991adade7Sdormando            was_found++;
51091adade7Sdormando        }
51191adade7Sdormando    }
51291adade7Sdormando
513eb75a0dfSPaul Lindner    if (it != NULL && settings.oldest_live != 0 && settings.oldest_live <= current_time &&
51456b8339eSSteven Grimm        it->time <= settings.oldest_live) {
51544ef96eeSPaul Lindner        do_item_unlink(it);           /* MTSAFE - cache_lock held */
516cab73e53SPaul Lindner        it = NULL;
51756b8339eSSteven Grimm    }
51891adade7Sdormando
51991adade7Sdormando    if (it == NULL && was_found) {
5206a48c213SManik Taneja        moxi_log_write(" -nuked by flush");
52191adade7Sdormando        was_found--;
52291adade7Sdormando    }
52391adade7Sdormando
524eb75a0dfSPaul Lindner    if (it != NULL && it->exptime != 0 && it->exptime <= current_time) {
52544ef96eeSPaul Lindner        do_item_unlink(it);           /* MTSAFE - cache_lock held */
526cab73e53SPaul Lindner        it = NULL;
52756b8339eSSteven Grimm    }
52856b8339eSSteven Grimm
52991adade7Sdormando    if (it == NULL && was_found) {
5306a48c213SManik Taneja        moxi_log_write(" -nuked by expire");
53191adade7Sdormando        was_found--;
53291adade7Sdormando    }
53391adade7Sdormando
534eb75a0dfSPaul Lindner    if (it != NULL) {
53556b8339eSSteven Grimm        it->refcount++;
53656b8339eSSteven Grimm        DEBUG_REFCNT(it, '+');
53756b8339eSSteven Grimm    }
53891adade7Sdormando
53991adade7Sdormando    if (settings.verbose > 2)
5406a48c213SManik Taneja        moxi_log_write("\n");
54191adade7Sdormando
54256b8339eSSteven Grimm    return it;
54356b8339eSSteven Grimm}
54456b8339eSSteven Grimm
5455da8dbabSTrond Norbye/** returns an item whether or not it's expired. */
546eb75a0dfSPaul Lindneritem *do_item_get_nocheck(const char *key, const size_t nkey) {
54756b8339eSSteven Grimm    item *it = assoc_find(key, nkey);
54856b8339eSSteven Grimm    if (it) {
54956b8339eSSteven Grimm        it->refcount++;
55056b8339eSSteven Grimm        DEBUG_REFCNT(it, '+');
55156b8339eSSteven Grimm    }
55256b8339eSSteven Grimm    return it;
55356b8339eSSteven Grimm}
55456b8339eSSteven Grimm
555c5944dc2SSteven Grimm/* expires items that are more recent than the oldest_live setting. */
55656b8339eSSteven Grimmvoid do_item_flush_expired(void) {
557c5944dc2SSteven Grimm    int i;
558c5944dc2SSteven Grimm    item *iter, *next;
55977dde9f9SPaul Lindner    if (settings.oldest_live == 0)
560c5944dc2SSteven Grimm        return;
561c5944dc2SSteven Grimm    for (i = 0; i < LARGEST_ID; i++) {
562c5944dc2SSteven Grimm        /* The LRU is sorted in decreasing time order, and an item's timestamp
563c5944dc2SSteven Grimm         * is never newer than its last access time, so we only need to walk
564c5944dc2SSteven Grimm         * back until we hit an item older than the oldest_live time.
565c5944dc2SSteven Grimm         * The oldest_live checking will auto-expire the remaining items.
566c5944dc2SSteven Grimm         */
567c5944dc2SSteven Grimm        for (iter = heads[i]; iter != NULL; iter = next) {
568c5944dc2SSteven Grimm            if (iter->time >= settings.oldest_live) {
569c5944dc2SSteven Grimm                next = iter->next;
570c5944dc2SSteven Grimm                if ((iter->it_flags & ITEM_SLABBED) == 0) {
57156b8339eSSteven Grimm                    do_item_unlink(iter);
572c5944dc2SSteven Grimm                }
573c5944dc2SSteven Grimm            } else {
574c5944dc2SSteven Grimm                /* We've hit the first old item. Continue to the next queue. */
575c5944dc2SSteven Grimm                break;
576c5944dc2SSteven Grimm            }
577c5944dc2SSteven Grimm        }
578c5944dc2SSteven Grimm    }
579c5944dc2SSteven Grimm}
580