1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */ 2 /* $Id$ */ 3 #include <sys/types.h> 4 #include <sys/stat.h> 5 #include <sys/time.h> 6 #include <sys/socket.h> 7 #include <sys/signal.h> 8 #include <sys/resource.h> 9 #include <fcntl.h> 10 #include <stdlib.h> 11 #include <stdio.h> 12 #include <string.h> 13 #include <unistd.h> 14 #include <netinet/in.h> 15 #include <errno.h> 16 #include <time.h> 17 #include <event.h> 18 #include <assert.h> 19 20 #include "memcached.h" 21 22 23 #define LARGEST_ID 255 24 static item *heads[LARGEST_ID]; 25 static item *tails[LARGEST_ID]; 26 unsigned int sizes[LARGEST_ID]; 27 28 void item_init(void) { 29 int i; 30 for(i=0; i<LARGEST_ID; i++) { 31 heads[i]=0; 32 tails[i]=0; 33 sizes[i]=0; 34 } 35 } 36 37 38 /* 39 * Generates the variable-sized part of the header for an object. 40 * 41 * suffix - Buffer for the "VALUE" line suffix (flags, size). 42 * nsuffix - The length of the suffix is stored here. 43 * keylen - The length of the key plus any padding required to word-align the 44 * "VALUE" suffix (which is done to speed up copying.) 45 * 46 * Returns the total size of the header. 47 */ 48 int item_make_header(char *key, int flags, int nbytes, 49 char *suffix, int *nsuffix, int *keylen) { 50 *keylen = strlen(key) + 1; if(*keylen % 4) *keylen += 4 - (*keylen % 4); 51 *nsuffix = sprintf(suffix, " %u %u\r\n", flags, nbytes - 2); 52 return sizeof(item) + *keylen + *nsuffix + nbytes; 53 } 54 55 item *item_alloc(char *key, int flags, rel_time_t exptime, int nbytes) { 56 int nsuffix, ntotal, len; 57 item *it; 58 unsigned int id; 59 char suffix[40]; 60 61 ntotal = item_make_header(key, flags, nbytes, suffix, &nsuffix, &len); 62 63 id = slabs_clsid(ntotal); 64 if (id == 0) 65 return 0; 66 67 it = slabs_alloc(ntotal); 68 if (it == 0) { 69 int tries = 50; 70 item *search; 71 72 /* If requested to not push old items out of cache when memory runs out, 73 * we're out of luck at this point... 74 */ 75 76 if (!settings.evict_to_free) return 0; 77 78 /* 79 * try to get one off the right LRU 80 * don't necessariuly unlink the tail because it may be locked: refcount>0 81 * search up from tail an item with refcount==0 and unlink it; give up after 50 82 * tries 83 */ 84 85 if (id > LARGEST_ID) return 0; 86 if (tails[id]==0) return 0; 87 88 for (search = tails[id]; tries>0 && search; tries--, search=search->prev) { 89 if (search->refcount==0) { 90 item_unlink(search); 91 break; 92 } 93 } 94 it = slabs_alloc(ntotal); 95 if (it==0) return 0; 96 } 97 98 assert(it->slabs_clsid == 0); 99 100 it->slabs_clsid = id; 101 102 assert(it != heads[it->slabs_clsid]); 103 104 it->next = it->prev = it->h_next = 0; 105 it->refcount = 0; 106 it->it_flags = 0; 107 it->nkey = len; 108 it->nbytes = nbytes; 109 strcpy(ITEM_key(it), key); 110 it->exptime = exptime; 111 memcpy(ITEM_suffix(it), suffix, nsuffix); 112 it->nsuffix = nsuffix; 113 return it; 114 } 115 116 void item_free(item *it) { 117 unsigned int ntotal = ITEM_ntotal(it); 118 assert((it->it_flags & ITEM_LINKED) == 0); 119 assert(it != heads[it->slabs_clsid]); 120 assert(it != tails[it->slabs_clsid]); 121 assert(it->refcount == 0); 122 123 /* so slab size changer can tell later if item is already free or not */ 124 it->slabs_clsid = 0; 125 it->it_flags |= ITEM_SLABBED; 126 slabs_free(it, ntotal); 127 } 128 129 /* 130 * Returns true if an item will fit in the cache (its size does not exceed 131 * the maximum for a cache entry.) 132 */ 133 int item_size_ok(char *key, int flags, int nbytes) { 134 char prefix[40]; 135 int keylen, nsuffix; 136 137 return slabs_clsid(item_make_header(key, flags, nbytes, 138 prefix, &nsuffix, &keylen)) != 0; 139 } 140 141 void item_link_q(item *it) { /* item is the new head */ 142 item **head, **tail; 143 /* always true, warns: assert(it->slabs_clsid <= LARGEST_ID); */ 144 assert((it->it_flags & ITEM_SLABBED) == 0); 145 146 head = &heads[it->slabs_clsid]; 147 tail = &tails[it->slabs_clsid]; 148 assert(it != *head); 149 assert((*head && *tail) || (*head == 0 && *tail == 0)); 150 it->prev = 0; 151 it->next = *head; 152 if (it->next) it->next->prev = it; 153 *head = it; 154 if (*tail == 0) *tail = it; 155 sizes[it->slabs_clsid]++; 156 return; 157 } 158 159 void item_unlink_q(item *it) { 160 item **head, **tail; 161 /* always true, warns: assert(it->slabs_clsid <= LARGEST_ID); */ 162 head = &heads[it->slabs_clsid]; 163 tail = &tails[it->slabs_clsid]; 164 165 if (*head == it) { 166 assert(it->prev == 0); 167 *head = it->next; 168 } 169 if (*tail == it) { 170 assert(it->next == 0); 171 *tail = it->prev; 172 } 173 assert(it->next != it); 174 assert(it->prev != it); 175 176 if (it->next) it->next->prev = it->prev; 177 if (it->prev) it->prev->next = it->next; 178 sizes[it->slabs_clsid]--; 179 return; 180 } 181 182 int item_link(item *it) { 183 assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0); 184 assert(it->nbytes < 1048576); 185 it->it_flags |= ITEM_LINKED; 186 it->time = current_time; 187 assoc_insert(ITEM_key(it), it); 188 189 stats.curr_bytes += ITEM_ntotal(it); 190 stats.curr_items += 1; 191 stats.total_items += 1; 192 193 item_link_q(it); 194 195 return 1; 196 } 197 198 void item_unlink(item *it) { 199 if (it->it_flags & ITEM_LINKED) { 200 it->it_flags &= ~ITEM_LINKED; 201 stats.curr_bytes -= ITEM_ntotal(it); 202 stats.curr_items -= 1; 203 assoc_delete(ITEM_key(it)); 204 item_unlink_q(it); 205 } 206 if (it->refcount == 0) item_free(it); 207 } 208 209 void item_remove(item *it) { 210 assert((it->it_flags & ITEM_SLABBED) == 0); 211 if (it->refcount) it->refcount--; 212 assert((it->it_flags & ITEM_DELETED) == 0 || it->refcount); 213 if (it->refcount == 0 && (it->it_flags & ITEM_LINKED) == 0) { 214 item_free(it); 215 } 216 } 217 218 void item_update(item *it) { 219 assert((it->it_flags & ITEM_SLABBED) == 0); 220 221 item_unlink_q(it); 222 it->time = current_time; 223 item_link_q(it); 224 } 225 226 int item_replace(item *it, item *new_it) { 227 assert((it->it_flags & ITEM_SLABBED) == 0); 228 229 item_unlink(it); 230 return item_link(new_it); 231 } 232 233 char *item_cachedump(unsigned int slabs_clsid, unsigned int limit, unsigned int *bytes) { 234 235 int memlimit = 2*1024*1024; 236 char *buffer; 237 int bufcurr; 238 item *it; 239 int len; 240 int shown = 0; 241 char temp[512]; 242 243 if (slabs_clsid > LARGEST_ID) return 0; 244 it = heads[slabs_clsid]; 245 246 buffer = malloc(memlimit); 247 if (buffer == 0) return 0; 248 bufcurr = 0; 249 250 while (it && (!limit || shown < limit)) { 251 len = sprintf(temp, "ITEM %s [%u b; %lu s]\r\n", ITEM_key(it), it->nbytes - 2, it->time + stats.started); 252 if (bufcurr + len + 6 > memlimit) /* 6 is END\r\n\0 */ 253 break; 254 strcpy(buffer + bufcurr, temp); 255 bufcurr+=len; 256 shown++; 257 it = it->next; 258 } 259 260 strcpy(buffer+bufcurr, "END\r\n"); 261 bufcurr+=5; 262 263 *bytes = bufcurr; 264 return buffer; 265 } 266 267 void item_stats(char *buffer, int buflen) { 268 int i; 269 char *bufcurr = buffer; 270 rel_time_t now = current_time; 271 272 if (buflen < 4096) { 273 strcpy(buffer, "SERVER_ERROR out of memory"); 274 return; 275 } 276 277 for (i=0; i<LARGEST_ID; i++) { 278 if (tails[i]) 279 bufcurr += sprintf(bufcurr, "STAT items:%u:number %u\r\nSTAT items:%u:age %u\r\n", 280 i, sizes[i], i, now - tails[i]->time); 281 } 282 strcpy(bufcurr, "END"); 283 return; 284 } 285 286 /* dumps out a list of objects of each size, with granularity of 32 bytes */ 287 char* item_stats_sizes(int *bytes) { 288 int num_buckets = 32768; /* max 1MB object, divided into 32 bytes size buckets */ 289 unsigned int *histogram = (unsigned int*) malloc(num_buckets * sizeof(int)); 290 char *buf = (char*) malloc(1024*1024*2*sizeof(char)); 291 int i; 292 293 if (histogram == 0 || buf == 0) { 294 if (histogram) free(histogram); 295 if (buf) free(buf); 296 return 0; 297 } 298 299 /* build the histogram */ 300 memset(histogram, 0, num_buckets * sizeof(int)); 301 for (i=0; i<LARGEST_ID; i++) { 302 item *iter = heads[i]; 303 while (iter) { 304 int ntotal = ITEM_ntotal(iter); 305 int bucket = ntotal / 32; 306 if (ntotal % 32) bucket++; 307 if (bucket < num_buckets) histogram[bucket]++; 308 iter = iter->next; 309 } 310 } 311 312 /* write the buffer */ 313 *bytes = 0; 314 for (i=0; i<num_buckets; i++) { 315 if (histogram[i]) { 316 *bytes += sprintf(&buf[*bytes], "%u %u\r\n", i*32, histogram[i]); 317 } 318 } 319 *bytes += sprintf(&buf[*bytes], "END\r\n"); 320 free(histogram); 321 return buf; 322 } 323