From 43614f5d7e0d18f553c0ee2a4e195d7b8f63be1f Mon Sep 17 00:00:00 2001 From: hunt Date: Tue, 17 May 2005 08:02:30 +0000 Subject: [PATCH] Rewritten maps and other updated files. --- runtime/Doxyfile | 10 +- runtime/current.c | 53 ++ runtime/io.c | 6 +- runtime/list.c | 124 +++++ runtime/map-keys.c | 416 ++++++++++++++++ runtime/map-values.c | 135 ++++++ runtime/map.c | 1093 +++++++++++++++--------------------------- runtime/map.h | 157 ++++-- runtime/print.c | 41 +- runtime/runtime.h | 8 + runtime/stack.c | 101 +++- runtime/string.c | 9 + 12 files changed, 1374 insertions(+), 779 deletions(-) create mode 100644 runtime/list.c create mode 100644 runtime/map-keys.c create mode 100644 runtime/map-values.c diff --git a/runtime/Doxyfile b/runtime/Doxyfile index 5854b4a8d..0e8d4f9e4 100644 --- a/runtime/Doxyfile +++ b/runtime/Doxyfile @@ -693,7 +693,7 @@ TREEVIEW_WIDTH = 250 # If the GENERATE_LATEX tag is set to YES (the default) Doxygen will # generate Latex output. -GENERATE_LATEX = NO +GENERATE_LATEX = YES # The LATEX_OUTPUT tag is used to specify where the LaTeX docs will be put. # If a relative path is entered the value of OUTPUT_DIRECTORY will be @@ -716,13 +716,13 @@ MAKEINDEX_CMD_NAME = makeindex # LaTeX documents. This may be useful for small projects and may help to # save some trees in general. -COMPACT_LATEX = NO +COMPACT_LATEX = YES # The PAPER_TYPE tag can be used to set the paper type that is used # by the printer. Possible values are: a4, a4wide, letter, legal and # executive. If left blank a4wide will be used. -PAPER_TYPE = a4wide +PAPER_TYPE = letter # The EXTRA_PACKAGES tag can be to specify one or more names of LaTeX # packages that should be included in the LaTeX output. @@ -741,13 +741,13 @@ LATEX_HEADER = # contain links (just like the HTML output) instead of page references # This makes the output suitable for online browsing using a pdf viewer. -PDF_HYPERLINKS = NO +PDF_HYPERLINKS = YES # If the USE_PDFLATEX tag is set to YES, pdflatex will be used instead of # plain latex in the generated Makefile. Set this option to YES to get a # higher quality PDF documentation. -USE_PDFLATEX = NO +USE_PDFLATEX = YES # If the LATEX_BATCHMODE tag is set to YES, doxygen will add the \\batchmode. # command to the generated LaTeX files. This will instruct LaTeX to keep diff --git a/runtime/current.c b/runtime/current.c index 78820c407..618c9fc99 100644 --- a/runtime/current.c +++ b/runtime/current.c @@ -30,5 +30,58 @@ unsigned long _stp_ret_addr (struct pt_regs *regs) else return 0; } + +#ifdef __x86_64__ +#include + +void _stp_print_regs(struct pt_regs * regs) +{ + unsigned long cr0 = 0L, cr2 = 0L, cr3 = 0L, cr4 = 0L, fs, gs, shadowgs; + unsigned int fsindex,gsindex; + unsigned int ds,cs,es; + + _stp_printf("\n"); + // print_modules(); + _stp_printf("Pid: %d, comm: %.20s %s\n", + current->pid, current->comm, system_utsname.release); + _stp_printf("RIP: %04lx:[<%016lx>] ", regs->cs & 0xffff, regs->rip); + _stp_symbol_print (regs->rip); + _stp_printf("\nRSP: %04lx:%016lx EFLAGS: %08lx\n", regs->ss, regs->rsp, regs->eflags); + _stp_printf("RAX: %016lx RBX: %016lx RCX: %016lx\n", + regs->rax, regs->rbx, regs->rcx); + _stp_printf("RDX: %016lx RSI: %016lx RDI: %016lx\n", + regs->rdx, regs->rsi, regs->rdi); + _stp_printf("RBP: %016lx R08: %016lx R09: %016lx\n", + regs->rbp, regs->r8, regs->r9); + _stp_printf("R10: %016lx R11: %016lx R12: %016lx\n", + regs->r10, regs->r11, regs->r12); + _stp_printf("R13: %016lx R14: %016lx R15: %016lx\n", + regs->r13, regs->r14, regs->r15); + + asm("movl %%ds,%0" : "=r" (ds)); + asm("movl %%cs,%0" : "=r" (cs)); + asm("movl %%es,%0" : "=r" (es)); + asm("movl %%fs,%0" : "=r" (fsindex)); + asm("movl %%gs,%0" : "=r" (gsindex)); + + rdmsrl(MSR_FS_BASE, fs); + rdmsrl(MSR_GS_BASE, gs); + rdmsrl(MSR_KERNEL_GS_BASE, shadowgs); + + asm("movq %%cr0, %0": "=r" (cr0)); + asm("movq %%cr2, %0": "=r" (cr2)); + asm("movq %%cr3, %0": "=r" (cr3)); + asm("movq %%cr4, %0": "=r" (cr4)); + + _stp_printf("FS: %016lx(%04x) GS:%016lx(%04x) knlGS:%016lx\n", + fs,fsindex,gs,gsindex,shadowgs); + _stp_printf("CS: %04x DS: %04x ES: %04x CR0: %016lx\n", cs, ds, es, cr0); + _stp_printf("CR2: %016lx CR3: %016lx CR4: %016lx\n", cr2, cr3, cr4); + _stp_print_flush(); +} +#endif /* __x86_64__ */ + + + /** @} */ #endif /* _CURRENT_C_ */ diff --git a/runtime/io.c b/runtime/io.c index effa750c5..7c8c5ac0c 100644 --- a/runtime/io.c +++ b/runtime/io.c @@ -27,7 +27,7 @@ static char _stp_lbuf[NR_CPUS][STP_LOG_BUF_LEN + 1]; void _stp_log (const char *fmt, ...) { - int num; + int num, ret; char *buf = &_stp_lbuf[smp_processor_id()][0]; va_list args; va_start(args, fmt); @@ -35,7 +35,9 @@ void _stp_log (const char *fmt, ...) va_end(args); buf[num] = '\0'; - _stp_ctrl_send(STP_REALTIME_DATA, buf, num + 1, t->pid); + ret = _stp_ctrl_send(STP_REALTIME_DATA, buf, num + 1, t->pid); + if (ret < 0) + atomic_inc (&_stp_transport_failures); } /** @} */ diff --git a/runtime/list.c b/runtime/list.c new file mode 100644 index 000000000..b26653ed1 --- /dev/null +++ b/runtime/list.c @@ -0,0 +1,124 @@ +#ifndef _LIST_C_ /* -*- linux-c -*- */ +#define _LIST_C_ + +#ifndef NEED_INT64_KEYS +#error Before including list.c, "#define KEY1_TYPE INT64" and include "map-keys.c" +#endif + +#if !defined(NEED_STRING_VALS) && !defined(NEED_INT64_VALS) +#error Before including list.c, "#define VALUE_TYPE" to "INT64" or "STRING and include "map-values.c" +#endif + +#include "map.c" + +/********************** List Functions *********************/ + +/** @addtogroup lists + * Lists are special cases of maps. + * @b Example: + * @include list.c + * @{ */ + +/** Create a new list. + * A list is a map that internally has an incrementing long key for each member. + * Lists do not wrap if elements are added to exceed their maximum size. + * @param max_entries The maximum number of entries allowed. Currently that number will + * be preallocated. If max_entries is 0, there will be no maximum and entries + * will be allocated dynamically. + * @param type Type of values stored in this list. + * @return A MAP on success or NULL on failure. + * @sa foreach + */ + +MAP _stp_list_new(unsigned max_entries, int type) +{ + MAP map = _stp_map_new_int64 (max_entries, type); + map->no_wrap = 1; + return map; +} + +/** Clears a list. + * All elements in the list are deleted. + * @param map + */ + +void _stp_list_clear(MAP map) +{ + if (map == NULL) + return; + + if (!list_empty(&map->head)) { + struct map_node *ptr = (struct map_node *)map->head.next; + + while (ptr && ptr != (struct map_node *)&map->head) { + struct map_node *next = (struct map_node *)ptr->lnode.next; + + /* remove node from old hash list */ + hlist_del_init(&ptr->hnode); + + /* remove from entry list */ + list_del(&ptr->lnode); + + list_add(&ptr->lnode, &map->pool); + + map->num--; + ptr = next; + } + } + + if (map->num != 0) { + _stp_log ("ERROR: list is supposed to be empty (has %d)\n", map->num); + } +} + +#ifdef NEED_STRING_VALS +/** Adds a C string to a list. + * @param map + * @param str + * @sa _stp_list_add() + */ + +inline void _stp_list_add_str(MAP map, char *str) +{ + _stp_map_key_int64 (map, map->num); + _stp_map_set_str(map, str); +} + +/** Adds a String to a list. + * @param map + * @param str String to add. + * @sa _stp_list_add() + */ + +inline void _stp_list_add_string (MAP map, String str) +{ + _stp_map_key_int64 (map, map->num); + _stp_map_set_str(map, str->buf); +} +#endif /* NEED_STRING_VALS */ + +#ifdef NEED_INT64_VALS +/** Adds an int64 to a list. + * @param map + * @param val + * @sa _stp_list_add() + */ + +inline void _stp_list_add_int64(MAP map, int64_t val) +{ + _stp_map_key_int64 (map, map->num); + _stp_map_set_int64(map, val); +} +#endif /* NEED_INT64_VALS */ + +/** Get the number of elements in a list. + * @param map + * @returns The number of elements in a list. + */ + +inline int _stp_list_size(MAP map) +{ + return map->num; +} +/** @} */ +#endif /* _LIST_C_ */ diff --git a/runtime/map-keys.c b/runtime/map-keys.c new file mode 100644 index 000000000..37308179e --- /dev/null +++ b/runtime/map-keys.c @@ -0,0 +1,416 @@ +/* -*- linux-c -*- */ + +#include "map.h" + +#define JOIN(x,y) JOINx(x,y) +#define JOINx(x,y) x##_##y + +#if defined (KEY1_TYPE) +#define KEY_ARITY 1 +#if KEY1_TYPE == STRING +#define KEY1TYPE char* +#define KEY1NAME str +#define KEY1STOR char key1[MAP_STRING_LENGTH] +#define NEED_STRING_KEYS +#else +#define KEY1TYPE int64_t +#define KEY1NAME int64 +#define KEY1STOR int64_t key1 +#define NEED_INT64_KEYS +#endif +#define KEY1_EQ_P JOIN(KEY1NAME,eq_p) +#define KEY1_HASH JOIN(KEY1NAME,hash) +#endif /* defined(KEY1_TYPE) */ + +#if defined (KEY2_TYPE) +#undef KEY_ARITY +#define KEY_ARITY 2 +#if KEY2_TYPE == STRING +#define KEY2TYPE char* +#define KEY2NAME str +#define KEY2STOR char key2[MAP_STRING_LENGTH] +#define NEED_STRING_KEYS +#else +#define KEY2TYPE int64_t +#define KEY2NAME int64 +#define KEY2STOR int64_t key2 +#define NEED_INT64_KEYS +#endif +#define KEY2_EQ_P JOIN(KEY2NAME,eq_p) +#define KEY2_HASH JOIN(KEY2NAME,hash) +#endif /* defined(KEY2_TYPE) */ + +#if defined (KEY3_TYPE) +#undef KEY_ARITY +#define KEY_ARITY 3 +#if KEY3_TYPE == STRING +#define KEY3TYPE char* +#define KEY3NAME str +#define KEY3STOR char key3[MAP_STRING_LENGTH] +#define NEED_STRING_KEYS +#else +#define KEY3TYPE int64_t +#define KEY3NAME int64 +#define KEY3STOR int64_t key3 +#define NEED_INT64_KEYS +#endif +#define KEY3_EQ_P JOIN(KEY3NAME,eq_p) +#define KEY3_HASH JOIN(KEY3NAME,hash) +#endif /* defined(KEY3_TYPE) */ + +#if defined (KEY4_TYPE) +#undef KEY_ARITY +#define KEY_ARITY 4 +#if KEY4_TYPE == STRING +#define KEY4TYPE char* +#define KEY4NAME str +#define KEY4STOR char key4[MAP_STRING_LENGTH] +#define NEED_STRING_KEYS +#else +#define KEY4TYPE int64_t +#define KEY4NAME int64 +#define KEY4STOR int64_t key4 +#define NEED_INT64_KEYS +#endif +#define KEY4_EQ_P JOIN(KEY4NAME,eq_p) +#define KEY4_HASH JOIN(KEY4NAME,hash) +#endif /* defined(KEY4_TYPE) */ + +#if defined (KEY5_TYPE) +#undef KEY_ARITY +#define KEY_ARITY 5 +#if KEY5_TYPE == STRING +#define KEY5TYPE char* +#define KEY5NAME str +#define KEY5STOR char key5[MAP_STRING_LENGTH] +#define NEED_STRING_KEYS +#else +#define KEY5TYPE int64_t +#define KEY5NAME int64 +#define KEY5STOR int64_t key5 +#define NEED_INT64_KEYS +#endif +#define KEY5_EQ_P JOIN(KEY5NAME,eq_p) +#define KEY5_HASH JOIN(KEY5NAME,hash) +#endif /* defined(KEY5_TYPE) */ + +#if KEY_ARITY == 1 +#define KEYSYM(x) JOIN(x,KEY1NAME) +#define ALLKEYS(x) x##1 +#define ALLKEYSD(x) KEY1TYPE x##1 +#elif KEY_ARITY == 2 +#define JOIN2(x,y,z) JOIN2x(x,y,z) +#define JOIN2x(x,y,z) x##_##y##_##z +#define KEYSYM(x) JOIN2(x,KEY1NAME,KEY2NAME) +#define ALLKEYS(x) x##1, x##2 +#define ALLKEYSD(x) KEY1TYPE x##1, KEY2TYPE x##2 +#elif KEY_ARITY == 3 +#define JOIN3(a,b,c,d) JOIN3x(a,b,c,d) +#define JOIN3x(a,b,c,d) a##_##b##_##c##_##d +#define KEYSYM(x) JOIN3(x,KEY1NAME,KEY2NAME,KEY3NAME) +#define ALLKEYS(x) x##1, x##2, x##3 +#define ALLKEYSD(x) KEY1TYPE x##1, KEY2TYPE x##2, KEY3TYPE x##3 +#elif KEY_ARITY == 4 +#define JOIN4(a,b,c,d,e) JOIN4x(a,b,c,d,e) +#define JOIN4x(a,b,c,d,e) a##_##b##_##c##_##d##_##e +#define KEYSYM(x) JOIN4(x,KEY1NAME,KEY2NAME,KEY3NAME,KEY4NAME) +#define ALLKEYS(x) x##1, x##2, x##3, x##4 +#define ALLKEYSD(x) KEY1TYPE x##1, KEY2TYPE x##2, KEY3TYPE x##3, KEY4TYPE x##4 +#elif KEY_ARITY == 5 +#define JOIN5(a,b,c,d,e,f) JOIN5x(a,b,c,d,e,f) +#define JOIN5x(a,b,c,d,e,f) a##_##b##_##c##_##d##_##e##_##f +#define KEYSYM(x) JOIN5(x,KEY1NAME,KEY2NAME,KEY3NAME,KEY4NAME,KEY5NAME) +#define ALLKEYS(x) x##1, x##2, x##3, x##4, x##5 +#define ALLKEYSD(x) KEY1TYPE x##1, KEY2TYPE x##2, KEY3TYPE x##3, KEY4TYPE x##4, KEY5TYPE x##5 +#endif + +/* */ +struct KEYSYM(map_node) { + /* list of other nodes in the map */ + struct list_head lnode; + /* list of nodes with the same hash value */ + struct hlist_node hnode; + /* pointer back to the map struct */ + struct map_root *map; + + KEY1STOR; +#if KEY_ARITY > 1 + KEY2STOR; +#if KEY_ARITY > 2 + KEY3STOR; +#if KEY_ARITY > 3 + KEY4STOR; +#if KEY_ARITY > 4 + KEY5STOR; +#endif +#endif +#endif +#endif +}; + +#define type_to_enum(type) \ + ({ \ + int ret; \ + if (__builtin_types_compatible_p (type, char*)) \ + ret = STRING; \ + else \ + ret = INT64; \ + ret; \ + }) + +static key_data KEYSYM(map_get_key) (struct map_node *mn, int n, int *type) +{ + key_data ptr; + struct KEYSYM(map_node) *m = (struct KEYSYM(map_node) *)mn; + + dbug ("m=%lx\n", (long)m); + if (n > KEY_ARITY || n < 1) { + if (type) + *type = END; + return (key_data)(int64_t)0; + } + + switch (n) { + case 1: + ptr = (key_data)m->key1; + if (type) + *type = type_to_enum(KEY1TYPE); + break; +#if KEY_ARITY > 1 + case 2: + ptr = (key_data)m->key2; + if (type) + *type = type_to_enum(KEY2TYPE); + + break; +#if KEY_ARITY > 2 + case 3: + ptr = (key_data)m->key3; + if (type) + *type = type_to_enum(KEY3TYPE); + break; +#if KEY_ARITY > 3 + case 4: + ptr = (key_data)m->key4; + if (type) + *type = type_to_enum(KEY4TYPE); + break; +#if KEY_ARITY > 4 + case 5: + ptr = (key_data)m->key5; + if (type) + *type = type_to_enum(KEY5TYPE); + break; +#endif +#endif +#endif +#endif + default: + ptr = (key_data)(int64_t)0; + if (type) + *type = END; + } + return ptr; +} + + +static void KEYSYM(map_copy_keys) (MAP map, struct map_node *n) +{ + struct KEYSYM(map_node) *m = (struct KEYSYM(map_node) *)n; +#if KEY1_TYPE == STRING + str_copy (m->key1, map->c_key[0].strp); +#else + m->key1 = map->c_key[0].val; +#endif +#if KEY_ARITY > 1 +#if KEY2_TYPE == STRING + str_copy (m->key2, map->c_key[1].strp); +#else + m->key2 = map->c_key[1].val; +#endif +#if KEY_ARITY > 2 +#if KEY3_TYPE == STRING + str_copy (m->key3, map->c_key[2].strp); +#else + m->key3 = map->c_key[2].val; +#endif +#if KEY_ARITY > 3 +#if KEY4_TYPE == STRING + str_copy (m->key4, map->c_key[3].strp); +#else + m->key4 = map->c_key[3].val; +#endif +#if KEY_ARITY > 4 +#if KEY5_TYPE == STRING + str_copy (m->key5, map->c_key[4].strp); +#else + m->key5 = map->c_key[4].val; +#endif +#endif +#endif +#endif +#endif +} + + +static unsigned int KEYSYM(hash) (ALLKEYSD(key)) +{ + unsigned int hash = KEY1_HASH(key1); +#if KEY_ARITY > 1 + hash ^= KEY2_HASH(key2); +#if KEY_ARITY > 2 + hash ^= KEY3_HASH(key3); +#if KEY_ARITY > 3 + hash ^= KEY4_HASH(key4); +#if KEY_ARITY > 4 + hash ^= KEY5_HASH(key5); +#endif +#endif +#endif +#endif + return (unsigned int) hash; +} + +/* _stp_map_new_key1_key2 (num, STAT, LINEAR, start, end, interval) */ +/* _stp_map_new_key1_key2 (num, STAT, LOG, buckets) */ + +MAP KEYSYM(_stp_map_new) (unsigned max_entries, int valtype, ...) +{ + int htype, buckets=0, start=0, stop=0, interval=0; + MAP m; + + htype = valtype >> 8; + dbug ("htype=%d\n", htype); + + if (htype != HIST_NONE) { + va_list ap; + va_start (ap, valtype); + + if (htype == HIST_LOG) { + buckets = va_arg(ap, int); + dbug ("buckets=%d\n", buckets); + } else { + start = va_arg(ap, int); + stop = va_arg(ap, int); + interval = va_arg(ap, int); + dbug ("start=%d stop=%d interval=%d\n", start, stop, interval); + } + va_end (ap); + } + switch (htype) { + case HIST_NONE: + m = _stp_map_new (max_entries, valtype & 0x0f, + sizeof(struct KEYSYM(map_node)), 0); + break; + case HIST_LOG: + m = _stp_map_new_hstat_log (max_entries, sizeof(struct KEYSYM(map_node)), + buckets); + break; + case HIST_LINEAR: + m = _stp_map_new_hstat_linear (max_entries, sizeof(struct KEYSYM(map_node)), + start, stop, interval); + break; + default: + dbug ("ERROR: unknown histogram type %d\n", htype); + m = NULL; + } + + if (m) { + m->copy_keys = KEYSYM(map_copy_keys); + m->get_key = KEYSYM(map_get_key); + } + return m; +} + + +#define SETKEYS2(key, n) { \ + if (__builtin_types_compatible_p (typeof (key), char[])) { \ + map->c_key[n].strp = (char *)key; \ + } else { \ + map->c_key[n].val = (int64_t)key; \ + } \ + } + +void KEYSYM(_stp_map_key) (MAP map, ALLKEYSD(key)) +{ + unsigned int hv; + struct hlist_head *head; + struct hlist_node *e; + + if (map == NULL) + return; + + hv = KEYSYM(hash) (ALLKEYS(key)); + head = &map->hashes[hv]; + + hlist_for_each(e, head) { + struct KEYSYM(map_node) *n = + (struct KEYSYM(map_node) *)((long)e - sizeof(struct hlist_node)); + //dbug ("n =%lx key=" EACHKEY(%ld) "\n", (long)n, n->key1.val, n->key2.val); + if (KEY1_EQ_P(n->key1, key1) +#if KEY_ARITY > 1 + && KEY2_EQ_P(n->key2, key2) +#if KEY_ARITY > 2 + && KEY3_EQ_P(n->key3, key3) +#if KEY_ARITY > 3 + && KEY4_EQ_P(n->key4, key4) +#if KEY_ARITY > 4 + && KEY5_EQ_P(n->key5, key5) +#endif +#endif +#endif +#endif + ) { + map->key = (struct map_node *)n; + dbug ("saving key %lx\n", (long)map->key); + map->create = 0; + return; + } + } + + dbug ("key not found\n"); + SETKEYS2 (key1, 0); +#if KEY_ARITY > 1 + SETKEYS2 (key2, 1); +#if KEY_ARITY > 2 + SETKEYS2 (key3, 2); +#if KEY_ARITY > 3 + SETKEYS2 (key4, 3); +#if KEY_ARITY > 4 + SETKEYS2 (key5, 4); +#endif +#endif +#endif +#endif + + map->c_keyhead = head; + map->create = 1; +} + + +#undef KEY1NAME +#undef KEY1TYPE +#undef KEY1_TYPE +#undef KEY1STOR + +#undef KEY2NAME +#undef KEY2TYPE +#undef KEY2_TYPE +#undef KEY2STOR + +#undef KEY3NAME +#undef KEY3TYPE +#undef KEY3_TYPE +#undef KEY3STOR + +#undef KEY4NAME +#undef KEY4TYPE +#undef KEY4_TYPE +#undef KEY4STOR + +#undef KEY5NAME +#undef KEY5TYPE +#undef KEY5_TYPE +#undef KEY5STOR + +#undef KEY_ARITY diff --git a/runtime/map-values.c b/runtime/map-values.c new file mode 100644 index 000000000..3d6af1349 --- /dev/null +++ b/runtime/map-values.c @@ -0,0 +1,135 @@ +/* -*- linux-c -*- */ + +#include "map.h" + +#if VALUE_TYPE == STRING +#define VALUETYPE char* +#define VALUENAME str +#define NEED_STRING_VALS +#elif VALUE_TYPE == INT64 +#define VALUETYPE int64_t +#define VALUENAME int64 +#define NEED_INT64_VALS +#elif VALUE_TYPE == STAT +#define VALUETYPE stat* +#define VALUENAME stat +#define NEED_STAT_VALS +#else +#error VALUE_TYPE has unimplemented value. +#endif + +#define VALSYM(x) JOIN(x,VALUENAME) +#define VALUE_TYPE_COPY JOIN(VALUENAME,copy) +#define VALUE_TYPE_ADD JOIN(VALUENAME,add) +#define VALUE_GET JOIN(VALUENAME,get) + +void VALSYM(__stp_map_set) (MAP map, VALUETYPE val, int add) +{ + struct map_node *m; + + if (map == NULL) + return; + + if (map->create) { + if (val == 0 && !map->no_wrap) + return; + + m = __stp_map_create (map); + if (!m) + return; + + /* set the value */ + dbug ("m=%lx offset=%lx\n", (long)m, (long)map->data_offset); + VALUE_TYPE_COPY((void *)((long)m + map->data_offset), val); + //m->val = val; + } else { + if (map->key == NULL) + return; + + if (val) { + if (add) + VALUE_TYPE_ADD((void *)((long)map->key + map->data_offset), val); + else + VALUE_TYPE_COPY((void *)((long)map->key + map->data_offset), val); + } else if (!add) { + /* setting value to 0 is the same as deleting */ + _stp_map_key_del(map); + } + } +} + +void VALSYM(_stp_map_set) (MAP map, VALUETYPE val) +{ + VALSYM(__stp_map_set)(map, val, 0); +} + + +#if VALUE_TYPE == STAT +/** Adds an int64 to a stats map */ +void VALSYM(_stp_map_add_int64) (MAP map, int64_t val) +{ + stat *d; + int n; + + if (map == NULL) + return; + + if (map->create) { + struct map_node *m = __stp_map_create (map); + if (!m) + return; + + /* set the value */ + d = (stat *)((long)m + map->data_offset); + d->count = 1; + d->sum = d->min = d->max = val; + } else { + if (map->key == NULL) + return; + d = (stat *)((long)map->key + map->data_offset); + d->count++; + d->sum += val; + if (val > d->max) + d->max = val; + if (val < d->min) + d->min = val; + } + /* histogram */ + switch (map->hist_type) { + case HIST_LOG: + n = msb64 (val); + if (n >= map->hist_buckets) + n = map->hist_buckets - 1; + d->histogram[n]++; + break; + case HIST_LINEAR: + n = (val - map->hist_start) / map->hist_int; + if (n < 0) + n = 0; + if (n >= map->hist_buckets) + n = map->hist_buckets - 1; + d->histogram[n]++; + default: + break; + } +} +#endif /* VALUE_TYPE == STAT */ + +void VALSYM(_stp_map_add) (MAP map, VALUETYPE val) +{ + VALSYM(__stp_map_set)(map, val, 1); +} + +VALUETYPE VALSYM(_stp_map_get) (MAP map) +{ + struct map_node *m; + if (map == NULL || map->create || map->key == NULL) + return 0; + dbug ("key %lx\n", (long)map->key); + m = (struct map_node *)map->key; + return VALUE_GET ((void *)((long)m + map->data_offset)); +} + +#undef VALUE_TYPE +#undef VALUETYPE +#undef VALUENAME diff --git a/runtime/map.c b/runtime/map.c index 25ad86201..6f6116f5e 100644 --- a/runtime/map.c +++ b/runtime/map.c @@ -5,40 +5,222 @@ * @brief Implements maps (associative arrays) and lists */ -#include "map.h" #include "alloc.c" -#include "string.c" static int map_sizes[] = { - sizeof(struct map_node_int64), - sizeof(struct map_node_stat), - sizeof(struct map_node_str), - 0 + sizeof(int64_t), + MAP_STRING_LENGTH, + sizeof(stat), + 0 }; -static unsigned string_hash(const char *key1, const char *key2) +#ifdef NEED_INT64_KEYS +unsigned int int64_hash (const int64_t v) +{ + return (unsigned int)hash_long ((unsigned long)v, HASH_TABLE_BITS); +} + +int int64_eq_p (int64_t key1, int64_t key2) +{ + return key1 == key2; +} +#endif /* NEED_INT64_KEYS */ + + +#ifdef NEED_INT64_VALS +void int64_copy (void *dest, int64_t val) +{ + *(int64_t *)dest = val; +} + +void int64_add (void *dest, int64_t val) +{ + *(int64_t *)dest += val; +} + +int64_t int64_get (void *ptr) +{ + return *(int64_t *)ptr; +} +#endif /* NEED_INT64_VALS */ + + +#ifdef NEED_STAT_VALS +void stat_copy (void *dest, stat *src) +{ + memcpy (dest, src, sizeof(stat)); +} + +void stat_add (void *dest, stat *src) +{ + stat *d = (stat *)dest; + + d->count =+ src->count; + d->sum += src->sum; + if (src->max > d->max) + d->max = src->max; + if (src->min < d->min) + d->min = src->min; + /* FIXME: do histogram */ +} + +stat *stat_get(void *ptr) +{ + return (stat *)ptr; +} + +/* implements a log base 2 function, or Most Significant Bit */ +/* with bits from 1 (lsb) to 64 (msb) */ +/* msb64(0) = 0 */ +/* msb64(1) = 1 */ +/* msb64(8) = 4 */ +/* msb64(512) = 10 */ + +int msb64(int64_t val) +{ + int res = 64; + + if (val == 0) + return 0; + + /* shortcut. most values will be 16-bit */ + if (val & 0xffffffffffff0000ull) { + if (!(val & 0xffffffff00000000ull)) { + val <<= 32; + res -= 32; + } + + if (!(val & 0xffff000000000000ull)) { + val <<= 16; + res -= 16; + } + } else { + val <<= 48; + res -= 48; + } + + if (!(val & 0xff00000000000000ull)) { + val <<= 8; + res -= 8; + } + + if (!(val & 0xf000000000000000ull)) { + val <<= 4; + res -= 4; + } + + if (!(val & 0xc000000000000000ull)) { + val <<= 2; + res -= 2; + } + + if (!(val & 0x8000000000000000ull)) { + val <<= 1; + res -= 1; + } + + return res; +} + +#endif /* NEED_STAT_VALS */ + +int64_t _stp_key_get_int64 (struct map_node *mn, int n) +{ + if (mn) + return (*mn->map->get_key)(mn, n, NULL).val; + return 0; +} + +char *_stp_key_get_str (struct map_node *mn, int n) +{ + if (mn) + return (*mn->map->get_key)(mn, n, NULL).strp; + return ""; +} + + + +#if defined(NEED_STRING_VALS) || defined (NEED_STRING_KEYS) +void str_copy(char *dest, char *src) +{ + int len = strlen(src); + if (len > MAP_STRING_LENGTH - 1) + len = MAP_STRING_LENGTH - 1; + strncpy (dest, src, len); + dest[len] = 0; +} +#endif + +#ifdef NEED_STRING_VALS +void str_add(void *dest, char *val) +{ + char *dst = (char *)dest; + int len = strlen(val); + int len1 = strlen(dst); + int num = MAP_STRING_LENGTH - 1 - len1; + + if (len > num) + len = num; + strncpy (&dst[len1], val, len); + dst[len + len1] = 0; +} + +char *str_get (void *ptr) +{ + return ptr; +} + +/** Set the current element's value to String. + * This sets the current element's value to a String. The map must have been created + * to hold int64s using _stp_map_new(xxx, STRING) + * + * If the element doesn't exist, it is created. If no current element (key) + * is set for the map, this function does nothing. + * @param map + * @param str String containing new value. + * @sa _stp_map_set() + */ + +void _stp_map_set_string (MAP map, String str) +{ + _stp_map_set_str (map, str->buf); +} + +#endif /* NEED_STRING_VALS */ + +#ifdef NEED_STRING_KEYS +int str_eq_p (char *key1, char *key2) +{ + return strncmp(key1, key2, MAP_STRING_LENGTH - 1) == 0; +} + +unsigned int str_hash(const char *key1) { int hash = 0, count = 0; char *v1 = (char *)key1; - char *v2 = (char *)key2; while (*v1 && count++ < 5) { hash += *v1++; } - while (v2 && *v2 && count++ < 5) { - hash += *v2++; - } - return hash_long((unsigned long)hash, HASH_TABLE_BITS); + return (unsigned int)hash_long((unsigned long)hash, HASH_TABLE_BITS); } +#endif /* NEED_STRING_KEYS */ -static unsigned mixed_hash(const char *key1, long key2) +int64_t _stp_get_int64(struct map_node *m) { - int hash = 0, count = 0; - char *v = (char *)key1; - while (v && *v && count++ < 5) - hash += *v++; - return hash_long((unsigned long)(hash ^ key2), HASH_TABLE_BITS); + return *(int64_t *)((long)m + m->map->data_offset); } +char *_stp_get_str(struct map_node *m) +{ + return (char *)((long)m + m->map->data_offset); +} + +stat *_stp_get_stat(struct map_node *m) +{ + return (stat *)((long)m + m->map->data_offset); +} + + /** @addtogroup maps * Implements maps (associative arrays) and lists * @{ @@ -54,9 +236,9 @@ static unsigned mixed_hash(const char *key1, long key2) * @return A MAP on success or NULL on failure. */ -MAP _stp_map_new(unsigned max_entries, enum valtype type) +static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size) { - size_t size; + int size; MAP m = (MAP) _stp_valloc(sizeof(struct map_root)); if (m == NULL) return NULL; @@ -69,45 +251,79 @@ MAP _stp_map_new(unsigned max_entries, enum valtype type) dbug ("map_new: unknown type %d\n", type); return NULL; } - if (max_entries) { void *tmp; int i; struct list_head *e; INIT_LIST_HEAD(&m->pool); - size = map_sizes[type]; + + /* size is the size of the map_node. */ + /* add space for the value. */ + key_size = ALIGN(key_size,4); + m->data_offset = key_size; + if (data_size == 0) + data_size = map_sizes[type]; + data_size = ALIGN(data_size,4); + size = key_size + data_size; + tmp = _stp_valloc(max_entries * size); for (i = max_entries - 1; i >= 0; i--) { e = i * size + tmp; dbug ("e=%lx\n", (long)e); list_add(e, &m->pool); + ((struct map_node *)e)->map = m; } m->membuf = tmp; } + if (type == STAT) + m->hist_type = HIST_NONE; return m; } -static void map_free_strings(MAP map, struct map_node *n) +MAP _stp_map_new_hstat_log (unsigned max_entries, int key_size, int buckets) { - struct map_node_str *m = (struct map_node_str *)n; - dbug ("n = %lx\n", (long)n); - if (map->type == STRING) { - dbug ("val STRING %lx\n", (long)m->str); - if (m->str) - _stp_free(m->str); - } - if (m->n.key1type == STR) { - dbug ("key1 STR %lx\n", (long)key1str(m)); - if (key1str(m)) - _stp_free(key1str(m)); + /* add size for buckets */ + int size = buckets * sizeof(int64_t) + sizeof(stat); + MAP m = _stp_map_new (max_entries, STAT, key_size, size); + if (m) { + m->hist_type = HIST_LOG; + m->hist_buckets = buckets; + if (buckets < 1 || buckets > 64) { + dbug ("histogram: Bad number of buckets. Must be between 1 and 64\n"); + m->hist_type = HIST_NONE; + return m; + } } - if (m->n.key2type == STR) { - dbug ("key2 STR %lx\n", (long)key2str(m)); - if (key2str(m)) - _stp_free(key2str(m)); + return m; +} + +MAP _stp_map_new_hstat_linear (unsigned max_entries, int ksize, int start, int stop, int interval) +{ + MAP m; + int size; + int buckets = (stop - start) / interval; + if ((stop - start) % interval) buckets++; + + /* add size for buckets */ + size = buckets * sizeof(int64_t) + sizeof(stat); + + m = _stp_map_new (max_entries, STAT, ksize, size); + if (m) { + m->hist_type = HIST_LINEAR; + m->hist_start = start; + m->hist_stop = stop; + m->hist_int = interval; + m->hist_buckets = buckets; + if (m->hist_buckets <= 0) { + dbug ("histogram: bad stop, start and/or interval\n"); + m->hist_type = HIST_NONE; + return m; + } + } + return m; } /** Deletes the current element. @@ -140,13 +356,7 @@ void _stp_map_key_del(MAP map) /* remove from entry list */ list_del(&m->lnode); - /* remove any allocated string storage */ - map_free_strings(map, (struct map_node *)map->key); - - if (map->maxnum) - list_add(&m->lnode, &map->pool); - else - _stp_free(m); + list_add(&m->lnode, &map->pool); map->key = NULL; map->num--; @@ -206,707 +416,174 @@ void _stp_map_del(MAP map) { if (map == NULL) return; - - if (!list_empty(&map->head)) { - struct map_node *ptr = (struct map_node *)map->head.next; - while (ptr && ptr != (struct map_node *)&map->head) { - map_free_strings(map, ptr); - ptr = (struct map_node *)ptr->lnode.next; - } - } _stp_vfree(map->membuf); _stp_vfree(map); } -/********************** KEY FUNCTIONS *********************/ - - -/** Set the map's key to two longs. - * This sets the current element based on a key of two strings. If the keys are - * not found, a new element will not be created until a _stp_map_set_xxx - * call. - * @param map - * @param key1 first key - * @param key2 second key - */ +#ifdef NEED_STAT_VALS -void _stp_map_key_long_long(MAP map, long key1, long key2) +static int needed_space(int64_t v) { - unsigned hv; - struct hlist_head *head; - struct hlist_node *e; + int space = 0; - if (map == NULL) - return; - - hv = hash_long(key1 ^ key2, HASH_TABLE_BITS); - head = &map->hashes[hv]; + if (v == 0) + return 1; - dbug ("hash for %ld,%ld is %d\n", key1, key2, hv); - - hlist_for_each(e, head) { - struct map_node *n = - (struct map_node *)((long)e - sizeof(struct hlist_node)); - dbug ("n =%lx key=%ld,%ld\n", (long)n, n->key1.val, n->key2.val); - if (key1 == n->key1.val && key2 == n->key2.val) { - map->key = n; - dbug ("saving key %lx\n", (long)map->key); - map->create = 0; - return; - } + if (v < 0) { + space++; + v = -v; } - - map->c_key1.val = key1; - map->c_key2.val = key2; - map->c_key1type = LONG; - map->c_key2type = LONG; - map->c_keyhead = head; - map->create = 1; + while (v) { + v /= 10; + space++; + } + return space; } -/** Set the map's key to two strings. - * This sets the current element based on a key of two strings. If the keys are - * not found, a new element will not be created until a _stp_map_set_xxx - * call. - * @param map - * @param key1 first key - * @param key2 second key - */ - -void _stp_map_key_str_str(MAP map, char *key1, char *key2) +static void reprint (int num, char *s) { - unsigned hv; - struct hlist_head *head; - struct hlist_node *e; - - if (map == NULL) - return; - - if (key1 == NULL) { - map->key = NULL; - return; + while (num > 0) { + _stp_print_cstr (s); + num--; } - - hv = string_hash(key1, key2); - head = &map->hashes[hv]; - - dbug ("hash for %s,%s is %d\n", key1, key2, hv); - - hlist_for_each(e, head) { - struct map_node *n = - (struct map_node *)((long)e - sizeof(struct hlist_node)); - dbug ("e =%lx key=%s,%s\n", (long)e, n->key1.str,n->key2.str); - if (strcmp(key1, n->key1.str) == 0 - && (key2 == NULL || strcmp(key2, n->key2.str) == 0)) { - map->key = n; - dbug ("saving key %lx\n", (long)map->key); - map->create = 0; - return; - } - } - - map->c_key1.str = key1; - map->c_key2.str = key2; - map->c_key1type = STR; - map->c_key2type = STR; - map->c_keyhead = head; - map->create = 1; } -/** Set the map's key to a string and a long. - * This sets the current element based on a key of a string and a long. If the keys are - * not found, a new element will not be created until a _stp_map_set_xxx - * call. - * @param map - * @param key1 first key - * @param key2 second key - */ +#define HIST_WIDTH 50 -void _stp_map_key_str_long(MAP map, char *key1, long key2) +void _stp_map_print_histogram (MAP map, stat *s) { - unsigned hv; - struct hlist_head *head; - struct hlist_node *e; + int scale, i, j, val_space, cnt_space; + int64_t val, v, max = 0; - if (map == NULL) + if (map->hist_type != HIST_LOG && map->hist_type != HIST_LINEAR) return; + /* get the maximum value, for scaling */ - if (key1 == NULL) { - map->key = NULL; - return; + for (i = 0; i < map->hist_buckets; i++) + if (s->histogram[i] > max) + max = s->histogram[i]; + + if (max <= HIST_WIDTH) + scale = 1; + else { + scale = max / HIST_WIDTH; + if (max % HIST_WIDTH) scale++; } - hv = mixed_hash(key1, key2); - head = &map->hashes[hv]; - - dbug ("hash for %s,%ld is %d\n", key1, key2, hv); + cnt_space = needed_space (max); + if (map->hist_type == HIST_LINEAR) + val_space = needed_space (map->hist_start + map->hist_int * (map->hist_buckets - 1)); + else + val_space = needed_space (1 << (map->hist_buckets - 1)); + dbug ("max=%lld scale=%d val_space=%d\n", max, scale, val_space); - hlist_for_each(e, head) { - struct map_node *n = - (struct map_node *)((long)e - sizeof(struct hlist_node)); - dbug ("e =%lx key=%s,%ld\n", (long)e, n->key1.str,(long)n->key2.val); - if (strcmp(key1, n->key1.str) == 0 && key2 == n->key2.val) { - map->key = n; - dbug ("saving key %lx\n", (long)map->key); - map->create = 0; - return; - } + /* print header */ + j = 0; + if (val_space > 5) /* 5 = sizeof("value") */ + j = val_space - 5; + else + val_space = 5; + for ( i = 0; i < j; i++) + _stp_print_cstr (" "); + _stp_print_cstr("value |"); + reprint (HIST_WIDTH, "-"); + _stp_print_cstr (" count\n"); + _stp_print_flush(); + if (map->hist_type == HIST_LINEAR) + val = map->hist_start; + else + val = 0; + for (i = 0; i < map->hist_buckets; i++) { + reprint (val_space - needed_space(val), " "); + _stp_printf("%d", val); + _stp_print_cstr (" |"); + v = s->histogram[i] / scale; + reprint (v, "@"); + reprint (HIST_WIDTH - v + 1 + cnt_space - needed_space(s->histogram[i]), " "); + _stp_printf ("%lld\n", s->histogram[i]); + if (map->hist_type == HIST_LINEAR) + val += map->hist_int; + else if (val == 0) + val = 1; + else + val *= 2; + _stp_print_flush(); } - - map->c_key1.str = key1; - map->c_key2.val = key2; - map->c_key1type = STR; - map->c_key2type = LONG; - map->c_keyhead = head; - map->create = 1; } +#endif /* NEED_STAT_VALS */ -/** Set the map's key to a long and a string. - * This sets the current element based on a key of a long and a string. If the keys are - * not found, a new element will not be created until a _stp_map_set_xxx - * call. - * @param map - * @param key1 first key - * @param key2 second key - */ - -void _stp_map_key_long_str(MAP map, long key1, char *key2) +void _stp_map_print (MAP map, const char *name) { - unsigned hv; - struct hlist_head *head; - struct hlist_node *e; - - if (map == NULL) - return; - - hv = mixed_hash(key2, key1); - head = &map->hashes[hv]; - dbug ("hash for %ld,%s is %d\n", key1, key2, hv); - - hlist_for_each(e, head) { - struct map_node *n = - (struct map_node *)((long)e - sizeof(struct hlist_node)); - dbug ("e =%lx key=%ld,%s\n", (long)e, n->key1.val,n->key2.str); - if (key1 == n->key1.val && strcmp(key2, n->key2.str) == 0) { - map->key = n; - dbug ("saving key %lx\n", (long)map->key); - map->create = 0; - return; + struct map_node *ptr; + int type, n, first; + key_data kd; + + dbug ("print map %lx\n", (long)map); + for (ptr = _stp_map_start(map); ptr; ptr = _stp_map_iter (map, ptr)) { + n = 1; first = 1; + _stp_print_cstr (name); + _stp_print_cstr ("["); + do { + kd = (*map->get_key)(ptr, n, &type); + if (type == END) + break; + if (!first) + _stp_print_cstr (", "); + first = 0; + if (type == STRING) + _stp_print_cstr (kd.strp); + else + _stp_printf("%lld", kd.val); + n++; + } while (1); + _stp_print_cstr ("] = "); + if (map->type == STRING) + _stp_print_cstr(_stp_get_str(ptr)); + else if (map->type == INT64) + _stp_printf("%d", _stp_get_int64(ptr)); +#ifdef NEED_STAT_VALS + else { + stat *s = _stp_get_stat(ptr); + _stp_printf("count:%lld sum:%lld avg:%lld min:%lld max:%lld\n", + s->count, s->sum, s->sum/s->count, s->min, s->max); + _stp_print_flush(); + _stp_map_print_histogram (map, s); } +#endif + _stp_print_cstr ("\n"); + _stp_print_flush(); } - - map->c_key1.val = key1; - map->c_key2.str = key2; - map->c_key1type = LONG; - map->c_key2type = STR; - map->c_keyhead = head; - map->create = 1; + _stp_print_cstr ("\n"); + _stp_print_flush(); } -/** Set the map's key to a string. - * This sets the current element based on a string key. If the key is - * not found, a new element will not be created until a _stp_map_set_xxx - * call. - * @param map - * @param key - */ - -void _stp_map_key_str(MAP map, char *key) +static struct map_node *__stp_map_create (MAP map) { - if (map == NULL) - return; - _stp_map_key_str_str(map, key, NULL); - map->c_key2type = NONE; -} - -/** Set the map's key to a long. - * This sets the current element based on a long key. If the key is - * not found, a new element will not be created until a _stp_map_set_xxx - * call. - * @param map - * @param key - */ - -void _stp_map_key_long(MAP map, long key) -{ - if (map == NULL) - return; - _stp_map_key_long_long(map, key, 0); - map->c_key2type = NONE; -} - -/********************** SET/GET VALUES *********************/ - -static void map_copy_keys(MAP map, struct map_node *m) -{ - m->key1type = map->c_key1type; - m->key2type = map->c_key2type; - switch (map->c_key1type) { - case STR: - m->key1.str = _stp_alloc(strlen(map->c_key1.str) + 1); - strcpy(m->key1.str, map->c_key1.str); - break; - case LONG: - m->key1.val = map->c_key1.val; - break; - case NONE: - /* ERROR */ - break; - } - switch (map->c_key2type) { - case STR: - m->key2.str = _stp_alloc(strlen(map->c_key2.str) + 1); - strcpy(m->key2.str, map->c_key2.str); - break; - case LONG: - m->key2.val = map->c_key2.val; - break; - case NONE: - break; + struct map_node *m; + if (list_empty(&map->pool)) { + if (map->no_wrap) { + /* ERROR. FIXME */ + return NULL; + } + m = (struct map_node *)map->head.next; + hlist_del_init(&m->hnode); + dbug ("got %lx off head\n", (long)m); + } else { + m = (struct map_node *)map->pool.next; + dbug ("got %lx off pool\n", (long)m); } - + list_move_tail(&m->lnode, &map->head); + + /* copy the key(s) */ + (map->copy_keys)(map, m); + /* add node to new hash list */ hlist_add_head(&m->hnode, map->c_keyhead); map->key = m; map->create = 0; map->num++; + return m; } +#endif -static void __stp_map_set_int64(MAP map, int64_t val, int add) -{ - struct map_node_int64 *m; - - if (map == NULL) - return; - - if (map->create) { - if (val == 0) - return; - - if (map->maxnum) { - if (list_empty(&map->pool)) { - if (map->no_wrap) { - /* ERROR. FIXME */ - return; - } - m = (struct map_node_int64 *)map->head.next; - hlist_del_init(&m->n.hnode); - map_free_strings(map, (struct map_node *)m); - dbug ("got %lx off head\n", (long)m); - } else { - m = (struct map_node_int64 *)map->pool.next; - dbug ("got %lx off pool\n", (long)m); - } - list_move_tail(&m->n.lnode, &map->head); - } else { - m = (struct map_node_int64 *) - _stp_calloc(sizeof(struct map_node_int64)); - /* add node to list */ - list_add_tail(&m->n.lnode, &map->head); - } - - /* copy the key(s) */ - map_copy_keys(map, &m->n); - - /* set the value */ - m->val = val; - } else { - if (map->key == NULL) - return; - - if (val) { - m = (struct map_node_int64 *)map->key; - if (add) - m->val += val; - else - m->val = val; - } else if (!add) { - /* setting value to 0 is the same as deleting */ - _stp_map_key_del(map); - } - } -} - -/** Set the current element's value to an int64. - * This sets the current element's value to an int64. The map must have been created - * to hold int64s using _stp_map_new() - * - * If the element doesn't exist, it is created. If no current element (key) - * is set for the map, this function does nothing. - * @param map - * @param val new value - * @sa _stp_map_add_int64 - * @sa _stp_map_set() - */ -void _stp_map_set_int64(MAP map, int64_t val) -{ - __stp_map_set_int64 (map, val, 0); -} - - -/** Adds an int64 to the current element's value. - * This adds an int64 to the current element's value. The map must have been created - * to hold int64s using _stp_map_new() - * - * If the element doesn't exist, it is created. If no current element (key) - * is set for the map, this function does nothing. - * @param map - * @param val value - * @sa _stp_map_set_int64 - */ - -void _stp_map_add_int64(MAP map, int64_t val) -{ - __stp_map_set_int64 (map, val, 1); -} - -/** Gets the current element's value. - * @param map - * @returns The value. If the current element is not set or doesn't exist, returns 0. - */ - -int64_t _stp_map_get_int64(MAP map) -{ - struct map_node_int64 *m; - if (map == NULL || map->create || map->key == NULL) - return 0; - dbug ("%lx\n", (long)map->key); - m = (struct map_node_int64 *)map->key; - return m->val; -} - -/** Set the current element's value to a C string. - * This sets the current element's value to an C string. The map must have been created - * to hold int64s using _stp_map_new(xxx, STRING) - * - * If the element doesn't exist, it is created. If no current element (key) - * is set for the map, this function does nothing. - * @param map - * @param val new string - * @sa _stp_map_set() - */ - -void _stp_map_set_str(MAP map, char *val) -{ - struct map_node_str *m; - - if (map == NULL) - return; - - if (map->create) { - if (val == NULL) - return; - - if (map->maxnum) { - if (list_empty(&map->pool)) { - if (map->no_wrap) { - /* ERROR. FIXME */ - return; - } - m = (struct map_node_str *)map->head.next; - hlist_del_init(&m->n.hnode); - map_free_strings(map, (struct map_node *)m); - dbug ("got %lx off head\n", (long)m); - } else { - m = (struct map_node_str *)map->pool.next; - dbug ("got %lx off pool\n", (long)m); - } - list_move_tail(&m->n.lnode, &map->head); - } else { - m = (struct map_node_str *) - _stp_calloc(sizeof(struct map_node_str)); - /* add node to list */ - list_add_tail(&m->n.lnode, &map->head); - } - - /* copy the key(s) */ - map_copy_keys(map, &m->n); - - /* set the value */ - m->str = _stp_alloc(strlen(val) + 1); - strcpy(m->str, val); - } else { - if (map->key == NULL) - return; - - if (val) { - m = (struct map_node_str *)map->key; - if (m->str) - _stp_free(m->str); - m->str = _stp_alloc(strlen(val) + 1); - strcpy(m->str, val); - } else { - /* setting value to 0 is the same as deleting */ - _stp_map_key_del(map); - } - } -} - -/** Set the current element's value to String. - * This sets the current element's value to a String. The map must have been created - * to hold int64s using _stp_map_new(xxx, STRING) - * - * If the element doesn't exist, it is created. If no current element (key) - * is set for the map, this function does nothing. - * @param map - * @param str String containing new value. - * @sa _stp_map_set() - */ - -void _stp_map_set_string (MAP map, String str) -{ - _stp_map_set_str (map, str->buf); -} - -/** Gets the current element's value. - * @param map - * @returns A string pointer. If the current element is not set or doesn't exist, returns NULL. - */ - -char *_stp_map_get_str(MAP map) -{ - struct map_node_str *m; - if (map == NULL || map->create || map->key == NULL) - return NULL; - dbug ("%lx\n", (long)map->key); - m = (struct map_node_str *)map->key; - return m->str; -} - -/** Set the current element's value to a stat. - * This sets the current element's value to an stat struct. The map must have been created - * to hold stats using _stp_map_new(xxx, STAT). This function would only be used - * if we wanted to set stats to something other than the normal initial values (count = 0, - * sum = 0, etc). It may be deleted if it doesn't turn out to be useful. - * @sa _stp_map_stat_add - * - * If the element doesn't exist, it is created. If no current element (key) - * is set for the map, this function does nothing. - * @param map - * @param stats pointer to stats struct. - * @todo Histograms don't work yet. - */ - -void _stp_map_set_stat(MAP map, stat * stats) -{ - struct map_node_stat *m; - - if (map == NULL) - return; - dbug ("set_stat %lx\n", (long)map->key); - - if (map->create) { - if (stats == NULL) - return; - - if (map->maxnum) { - if (list_empty(&map->pool)) { - if (map->no_wrap) { - /* ERROR. FIXME */ - return; - } - m = (struct map_node_stat *)map->head.next; - hlist_del_init(&m->n.hnode); - map_free_strings(map, (struct map_node *)m); - dbug ("got %lx off head\n", (long)m); - } else { - m = (struct map_node_stat *)map->pool.next; - dbug ("got %lx off pool\n", (long)m); - } - list_move_tail(&m->n.lnode, &map->head); - } else { - m = (struct map_node_stat *) - _stp_calloc(sizeof(struct map_node_stat)); - /* add node to list */ - list_add_tail(&m->n.lnode, &map->head); - } - - /* copy the key(s) */ - map_copy_keys(map, &m->n); - - /* set the value */ - memcpy(&m->stats, stats, sizeof(stat)); - } else { - if (map->key == NULL) - return; - - if (stats) { - m = (struct map_node_stat *)map->key; - memcpy(&m->stats, stats, sizeof(stat)); - } else { - /* setting value to NULL is the same as deleting */ - _stp_map_key_del(map); - } - } -} - -/** Gets the current element's value. - * @param map - * @returns A pointer to the stats struct. If the current element is not set - * or doesn't exist, returns NULL. - */ - -stat *_stp_map_get_stat(MAP map) -{ - struct map_node_stat *m; - if (map == NULL || map->create || map->key == NULL) - return NULL; - dbug ("%lx\n", (long)map->key); - m = (struct map_node_stat *)map->key; - return &m->stats; -} - -/** Add to the current element's statistics. - * Increments the statistics counter by one and the sum by val. - * Adjusts minimum, maximum, and histogram. - * - * If the element doesn't exist, it is created. If no current element (key) - * is set for the map, this function does nothing. - * @param map - * @param val value to add to the statistics - * @todo Histograms don't work yet. - */ - -void _stp_map_stat_add(MAP map, int64_t val) -{ - struct map_node_stat *m; - if (map == NULL) - return; - - if (map->create) { - stat st = { 1, val, val, val }; - /* histogram */ - _stp_map_set_stat(map, &st); - return; - } - - if (map->key == NULL) - return; - - dbug ("add_stat %lx\n", (long)map->key); - m = (struct map_node_stat *)map->key; - m->stats.count++; - m->stats.sum += val; - if (val > m->stats.max) - m->stats.max = val; - if (val < m->stats.min) - m->stats.min = val; - /* histogram */ -} - -/** @} */ - -/********************** List Functions *********************/ - -/** @addtogroup lists - * Lists are special cases of maps. - * @b Example: - * @include list.c - * @{ */ - -/** Create a new list. - * A list is a map that internally has an incrementing long key for each member. - * Lists do not wrap if elements are added to exceed their maximum size. - * @param max_entries The maximum number of entries allowed. Currently that number will - * be preallocated. If max_entries is 0, there will be no maximum and entries - * will be allocated dynamically. - * @param type Type of values stored in this list. - * @return A MAP on success or NULL on failure. - * @sa foreach - */ - -MAP _stp_list_new(unsigned max_entries, enum valtype type) -{ - MAP map = _stp_map_new (max_entries, type); - map->no_wrap = 1; - return map; -} - -/** Clears a list. - * All elements in the list are deleted. - * @param map - */ - -void _stp_list_clear(MAP map) -{ - if (map == NULL) - return; - - if (!list_empty(&map->head)) { - struct map_node *ptr = (struct map_node *)map->head.next; - - while (ptr && ptr != (struct map_node *)&map->head) { - struct map_node *next = (struct map_node *)ptr->lnode.next; - - /* remove node from old hash list */ - hlist_del_init(&ptr->hnode); - - /* remove from entry list */ - list_del(&ptr->lnode); - - /* remove any allocated string storage */ - map_free_strings(map, ptr); - - if (map->maxnum) - list_add(&ptr->lnode, &map->pool); - else - _stp_free(ptr); - - map->num--; - ptr = next; - } - } - - if (map->num != 0) { - _stp_log ("ERROR: list is supposed to be empty (has %d)\n", map->num); - } -} - -/** Adds a C string to a list. - * @param map - * @param str - * @sa _stp_list_add() - */ - -inline void _stp_list_add_str(MAP map, char *str) -{ - _stp_map_key_long(map, map->num); - _stp_map_set_str(map, str); -} - -/** Adds a String to a list. - * @param map - * @param str String to add. - * @sa _stp_list_add() - */ - -inline void _stp_list_add_string (MAP map, String str) -{ - _stp_map_key_long(map, map->num); - _stp_map_set_str(map, str->buf); -} - -/** Adds an int64 to a list. - * @param map - * @param val - * @sa _stp_list_add() - */ - -inline void _stp_list_add_int64(MAP map, int64_t val) -{ - _stp_map_key_long(map, map->num); - _stp_map_set_int64(map, val); -} - -/** Get the number of elements in a list. - * @param map - * @returns The number of elements in a list. - */ - -inline int _stp_list_size(MAP map) -{ - return map->num; -} -/** @} */ -#endif /* _MAP_C_ */ diff --git a/runtime/map.h b/runtime/map.h index 6b21e299b..e48ec5747 100644 --- a/runtime/map.h +++ b/runtime/map.h @@ -6,29 +6,47 @@ */ /** @addtogroup maps * @todo Needs to be made SMP-safe for when the big lock is removed from kprobes. - * @{ + * @{ */ -#include +#ifndef HASH_TABLE_BITS +#define HASH_TABLE_BITS 8 +#define HASH_TABLE_SIZE (1<n.key1.str) +#define key1str(ptr) (_stp_key_get_str(ptr,1)) /** Extracts string from key2 union */ -#define key2str(ptr) (ptr->n.key2.str) +#define key2str(ptr) (_stp_key_get_str(ptr,2)) /** Extracts int from key1 union */ -#define key1int(ptr) (ptr->n.key1.val) +#define key1int(ptr) (_stp_key_get_int64(ptr,1)) /** Extracts int from key2 union */ -#define key2int(ptr) (ptr->n.key2.val) +#define key2int(ptr) (_stp_key_get_int64(ptr,2)) /** Macro to call the proper _stp_map_key functions based on the * types of the arguments. @@ -143,7 +150,7 @@ typedef struct map_root *MAP; if (__builtin_types_compatible_p (typeof (key), char[])) \ _stp_map_key_str (map, (char *)(key)); \ else \ - _stp_map_key_long (map, (long)(key)); \ + _stp_map_key_int64 (map, (int64_t)(key)); \ }) /** Macro to call the proper _stp_map_set function based on the @@ -180,6 +187,7 @@ typedef struct map_root *MAP; * * @note May cause compiler warning on some GCCs */ + #define _stp_list_add(map, val) \ ({ \ if (__builtin_types_compatible_p (typeof (val), char[])) \ @@ -190,4 +198,47 @@ typedef struct map_root *MAP; _stp_list_add_int64 (map, (int64_t)(val)); \ }) + +/************* prototypes for map.c ****************/ + +int int64_eq_p(int64_t key1, int64_t key2); +void int64_copy(void *dest, int64_t val); +void int64_add(void *dest, int64_t val); +int64_t int64_get(void *ptr); +void stat_copy(void *dest, stat *src); +void stat_add(void *dest, stat *src); +stat * stat_get(void *ptr); +int64_t _stp_key_get_int64(struct map_node *mn, int n); +char * _stp_key_get_str(struct map_node *mn, int n); +unsigned int int64_hash(const int64_t v); +char * str_get(void *ptr); +void str_copy(char *dest, char *src); +void str_add(void *dest, char *val); +int str_eq_p(char *key1, char *key2); +int64_t _stp_get_int64(struct map_node *m); +char * _stp_get_str(struct map_node *m); +stat * _stp_get_stat(struct map_node *m); +int msb64(int64_t x); +unsigned int str_hash(const char *key1); +static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size); +MAP _stp_map_new_hstat_log(unsigned max_entries, int key_size, int buckets); +MAP _stp_map_new_hstat_linear(unsigned max_entries, int ksize, int start, int stop, int interval); +void _stp_map_key_del(MAP map); +struct map_node * _stp_map_start(MAP map); +struct map_node * _stp_map_iter(MAP map, struct map_node *m); +void _stp_map_del(MAP map); +void _stp_map_print_histogram(MAP map, stat *s); +void _stp_map_print(MAP map, const char *name); +static struct map_node * __stp_map_create(MAP map); + +/* these prototypes suppress warnings from macros */ +void _stp_map_key_str(MAP, char *); +void _stp_map_set_str(MAP, char *); +void _stp_map_set_string(MAP, String); +void _stp_list_add_str(MAP, char*); +void _stp_list_add_string(MAP, String); + +void _stp_map_key_int64(MAP, int64_t); +void _stp_map_set_int64(MAP, int64_t); +int64_t _stp_map_get_int64(MAP); #endif /* _MAP_H_ */ diff --git a/runtime/print.c b/runtime/print.c index b6fd43231..cb5b3bc96 100644 --- a/runtime/print.c +++ b/runtime/print.c @@ -23,6 +23,36 @@ static int _stp_pbuf_len[NR_CPUS]; +#ifdef STP_NETLINK_ONLY +#define STP_PRINT_BUF_START 0 +static char _stp_pbuf[NR_CPUS][STP_PRINT_BUF_LEN + 1]; + +void _stp_print_flush (void) +{ + int cpu = smp_processor_id(); + char *buf = &_stp_pbuf[cpu][0]; + int len = _stp_pbuf_len[cpu]; + int ret; + + if (len == 0) + return; + + /* enforce newline at end */ + if (buf[len - 1] != '\n') { + buf[len++] = '\n'; + buf[len] = '\0'; + } + + ret = _stp_transport_write(t, buf, len + 1); + if (ret < 0) { + printk("flush: ret=%d.\n", ret); + atomic_inc (&_stp_transport_failures); + } + + _stp_pbuf_len[cpu] = 0; +} + +#else /* ! STP_NETLINK_ONLY */ /* size of timestamp, in bytes, including space */ #define TIMESTAMP_SIZE 19 #define STP_PRINT_BUF_START (TIMESTAMP_SIZE + 1) @@ -32,9 +62,10 @@ static char _stp_pbuf[NR_CPUS][STP_PRINT_BUF_LEN + STP_PRINT_BUF_START + 1]; * Output accumulates in the print buffer until this is called. * Size is limited by length of print buffer, #STP_PRINT_BUF_LEN. */ + void _stp_print_flush (void) { - int cpu = smp_processor_id(); + int ret, cpu = smp_processor_id(); char *buf = &_stp_pbuf[cpu][0]; char *ptr = buf + STP_PRINT_BUF_START; struct timeval tv; @@ -51,9 +82,15 @@ void _stp_print_flush (void) do_gettimeofday(&tv); scnprintf (buf, TIMESTAMP_SIZE+1, "[%li.%06li] ", tv.tv_sec, tv.tv_usec); buf[TIMESTAMP_SIZE] = ' '; - _stp_transport_write(t, buf, _stp_pbuf_len[cpu] + TIMESTAMP_SIZE + 2); + ret = _stp_transport_write(t, buf, _stp_pbuf_len[cpu] + TIMESTAMP_SIZE + 2); + if (ret < 0) { + printk("flush: ret=%d\n", ret); + atomic_inc (&_stp_transport_failures); + } + _stp_pbuf_len[cpu] = 0; } +#endif /* STP_NETLINK_ONLY */ /** Print into the print buffer. * Like printf, except output goes to the print buffer. diff --git a/runtime/runtime.h b/runtime/runtime.h index ee92c8dcf..d420fc1f7 100644 --- a/runtime/runtime.h +++ b/runtime/runtime.h @@ -5,6 +5,7 @@ */ #include +#include #include #include #include @@ -21,6 +22,13 @@ #define dbug(args...) ; +/* atomic globals */ +static atomic_t _stp_transport_failures = ATOMIC_INIT (0); + +/* some relayfs defaults that don't belong here */ +static unsigned n_subbufs = 4; +static unsigned subbuf_size = 65536; + #include "print.c" #endif /* _RUNTIME_H_ */ diff --git a/runtime/stack.c b/runtime/stack.c index e63d1d8b1..f06475dc7 100644 --- a/runtime/stack.c +++ b/runtime/stack.c @@ -14,16 +14,85 @@ static int (*_stp_kta)(unsigned long addr)=(void *)KTA; + +struct frame_head { + struct frame_head * ebp; + unsigned long ret; +} __attribute__((packed)); + +static struct frame_head * +dump_backtrace(struct frame_head * head) +{ + _stp_printf ("db: %lx\n", head->ret); + + /* frame pointers should strictly progress back up the stack + * (towards higher addresses) */ + if (head >= head->ebp) + return NULL; + + return head->ebp; +} + +static int pages_present(struct frame_head * head) +{ + struct mm_struct * mm = current->mm; + + /* FIXME: only necessary once per page */ + if (!check_user_page_readable(mm, (unsigned long)head)) + return 0; + + return check_user_page_readable(mm, (unsigned long)(head + 1)); +} + +static int valid_kernel_stack(struct frame_head * head, struct pt_regs * regs) +{ + unsigned long headaddr = (unsigned long)head; + unsigned long stack = (unsigned long)regs; + unsigned long stack_base = (stack & ~(THREAD_SIZE - 1)) + THREAD_SIZE; + _stp_log ("%lx %lx %lx\n", headaddr, stack, stack_base); + return headaddr < stack_base; +} + +void +x86_backtrace(struct pt_regs * const regs, unsigned int depth) +{ + struct frame_head *head; + +#ifdef CONFIG_X86_64 + head = (struct frame_head *)regs->rbp; +#else + head = (struct frame_head *)regs->ebp; +#endif + + if (!user_mode(regs)) { + _stp_log ("kernel mode\n"); + while (depth-- && valid_kernel_stack(head, regs)) + head = dump_backtrace(head); + _stp_print_flush(); + return; + } + +#ifdef CONFIG_SMP + if (!spin_trylock(¤t->mm->page_table_lock)) + return; +#endif + + while (depth-- && head && pages_present(head)) + head = dump_backtrace(head); + +#ifdef CONFIG_SMP + spin_unlock(¤t->mm->page_table_lock); +#endif + _stp_print_flush(); +} + + #ifdef __x86_64__ static void __stp_stack_print (unsigned long *stack, int verbose, int levels) { unsigned long addr; - - if (verbose) - _stp_printf ("trace for %d (%s)\n", current->pid, current->comm); - while (((long) stack & (THREAD_SIZE-1)) != 0) { - addr = *stack++; + addr = *stack; if (_stp_kta(addr)) { if (verbose) { _stp_symbol_print (addr); @@ -31,6 +100,7 @@ static void __stp_stack_print (unsigned long *stack, int verbose, int levels) } else _stp_printf ("0x%lx ", addr); } + stack++; } _stp_print_flush(); } @@ -42,10 +112,11 @@ static void __stp_stack_sprint (String str, unsigned long *stack, int verbose, i while (((long) stack & (THREAD_SIZE-1)) != 0) { addr = *stack++; if (_stp_kta(addr)) { - if (verbose) + if (verbose) { _stp_symbol_sprint (str, addr); - else - _stp_sprintf (str, "0x%lx ", addr); + _stp_sprintf (str, "\n"); + } else + _stp_sprintf (str, "0x%lx\n", addr); } } } @@ -153,12 +224,24 @@ static void __stp_stack_sprint (String str, unsigned long *stack, int verbose, i * @bug levels parameter is not functional */ -void _stp_stack_print (int verbose, int levels) +void _stp_stack_jprint (int verbose, int levels) { unsigned long stack; __stp_stack_print (&stack, verbose, levels); } +void _stp_stack_print (struct pt_regs *regs, int verbose, int levels) +{ + if (verbose) { + _stp_printf ("trace for %d (%s)\n", current->pid, current->comm); + _stp_symbol_print (regs->rip); + _stp_print ("\n"); + } else + _stp_printf ("0x%lx ", regs->rip); + + __stp_stack_print ((unsigned long *)regs->rsp, verbose, levels); +} + /** Writes stack dump to a String * * @param str String diff --git a/runtime/string.c b/runtime/string.c index b6432b763..574daac37 100644 --- a/runtime/string.c +++ b/runtime/string.c @@ -127,6 +127,15 @@ void _stp_string_cat_string (String str1, String str2) str1->len += num; } + +void _stp_string_to_ascii (String str) +{ + char *ptr = str->buf; + int num = str->len; + while (num--) + *ptr = toascii(*ptr); +} + /** Get a pointer to String's buffer * For rare cases when a C string is needed and you have a String. * One example is when you want to print a String with _stp_printf(). -- 2.43.5