1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
/* -*- linux-c -*-
* Map Header File
* Copyright (C) 2005 Red Hat Inc.
*
* This file is part of systemtap, and is free software. You can
* redistribute it and/or modify it under the terms of the GNU General
* Public License (GPL); either version 2, or (at your option) any
* later version.
*/
#ifndef _MAP_H_
#define _MAP_H_
/** @file map.h
* @brief Header file for maps and lists
*/
/** @addtogroup maps
* @todo Needs a spinlock variable to help when locks are required on the map.
* @{
*/
/* Include map spinlocks only on demand. Otherwise, assume that
caller does the right thing. */
#ifndef NEED_MAP_LOCKS
#define NEED_MAP_LOCKS 0
#endif
#if NEED_MAP_LOCKS
#define MAP_GET_CPU() get_cpu()
#define MAP_PUT_CPU() put_cpu()
#else
/* get/put_cpu wrappers. Unnecessary if caller is already atomic. */
#define MAP_GET_CPU() smp_processor_id()
#define MAP_PUT_CPU() do {} while (0)
#endif
/* This sets the size of the hash table. */
#ifndef HASH_TABLE_BITS
#define HASH_TABLE_BITS 8
/* This sets the size of the hash table. */
#define HASH_TABLE_SIZE (1<<HASH_TABLE_BITS)
#endif
/* The maximum number of keys allowed. Reducing this can save a small
amount of memory. Do not increase above 5. */
#ifndef MAX_KEY_ARITY
#define MAX_KEY_ARITY 5
#endif
/** Maximum length of strings in maps. This sets the amount of space
reserved for each string. This should match MAXSTRINGLEN. If
MAP_STRING_LENGTH is less than MAXSTRINGLEN, a user could get
strings truncated that are stored in arrays. */
#ifndef MAP_STRING_LENGTH
#define MAP_STRING_LENGTH MAXSTRINGLEN
#endif
/** @cond DONT_INCLUDE */
#define INT64 0
#define STRING 1
#define STAT 2
#define END 3
/** @endcond */
#include "stat.h"
/* Keys are either int64 or strings */
typedef union {
int64_t val;
char *strp;
} key_data;
/* basic map element */
struct 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;
};
/* This structure contains all information about a map.
* It is allocated once when _stp_map_new() is called.
*/
struct map_root {
/* type of the value stored in the array */
int type;
/* maximum number of elements allowed in the array. */
int maxnum;
/* current number of used elements */
int num;
/* when more than maxnum elements, wrap or discard? */
int wrap;
/* is this a list? */
int list;
/* linked list of current entries */
struct list_head head;
/* pool of unused entries. */
struct list_head pool;
/* saved key entry for lookups */
struct map_node *key;
/* This is information about the structure of the map_nodes used */
/* for this map. It is stored here instead of the map_node to save */
/* space. */
void (*copy_keys)(struct map_root *, struct map_node *);
key_data (*get_key)(struct map_node *mn, int n, int *type);
void (*copy)(struct map_node *dst, struct map_node *src);
int (*cmp)(struct map_node *dst, struct map_node *src);
int data_offset;
#ifdef NEED_MAP_LOCKS
spinlock_t lock;
#endif
/* the hash table for this array */
struct hlist_head hashes[HASH_TABLE_SIZE];
/* used if this map's nodes contain stats */
struct _Hist hist;
};
/** All maps are of this type. */
typedef struct map_root *MAP;
struct pmap {
MAP map; /* per-cpu maps */
struct map_root agg; /* aggregation map */
};
typedef struct pmap *PMAP;
/** Extracts string from key1 union */
#define key1str(ptr) (_stp_key_get_str(ptr,1))
/** Extracts string from key2 union */
#define key2str(ptr) (_stp_key_get_str(ptr,2))
/** Extracts int from key1 union */
#define key1int(ptr) (_stp_key_get_int64(ptr,1))
/** Extracts int from key2 union */
#define key2int(ptr) (_stp_key_get_int64(ptr,2))
/** Loop through all elements of a map or list.
* @param map
* @param ptr pointer to a map_node_stat, map_node_int64 or map_node_str
*
* @b Example:
* @include foreach.c
*/
#define foreach(map, ptr) \
for (ptr = _stp_map_start(map); ptr; ptr = _stp_map_iter (map, ptr))
/** @} */
/** @cond DONT_INCLUDE */
/************* prototypes for map.c ****************/
static 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);
static int64_t _stp_key_get_int64(struct map_node *mn, int n);
static char * _stp_key_get_str(struct map_node *mn, int n);
static unsigned int int64_hash(const int64_t v);
char * str_get(void *ptr);
static void str_copy(char *dest, char *src);
static void str_add(void *dest, char *val);
static int str_eq_p(char *key1, char *key2);
static int64_t _stp_get_int64(struct map_node *m);
static char * _stp_get_str(struct map_node *m);
static stat *_stp_get_stat(struct map_node *m);
static unsigned int str_hash(const char *key1);
static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size);
static PMAP _stp_pmap_new(unsigned max_entries, int type, int key_size, int data_size);
static int msb64(int64_t x);
static MAP _stp_map_new_hstat_log(unsigned max_entries, int key_size);
static MAP _stp_map_new_hstat_linear(unsigned max_entries, int ksize, int start, int stop, int interval);
static void _stp_map_print_histogram(MAP map, stat *s);
static struct map_node * _stp_map_start(MAP map);
static struct map_node * _stp_map_iter(MAP map, struct map_node *m);
static void _stp_map_del(MAP map);
static void _stp_map_clear(MAP map);
void _stp_map_print(MAP map, const char *fmt);
static struct map_node *_new_map_create (MAP map, struct hlist_head *head);
static int _new_map_set_int64 (MAP map, struct map_node *n, int64_t val, int add);
static int _new_map_set_str (MAP map, struct map_node *n, char *val, int add);
static void _new_map_clear_node (struct map_node *);
static void _new_map_del_node (MAP map, struct map_node *n);
static PMAP _stp_pmap_new_hstat_linear (unsigned max_entries, int ksize, int start, int stop, int interval);
static PMAP _stp_pmap_new_hstat_log (unsigned max_entries, int key_size);
static void _stp_add_agg(struct map_node *aptr, struct map_node *ptr);
static struct map_node *_stp_new_agg(MAP agg, struct hlist_head *ahead, struct map_node *ptr);
static void __stp_map_del(MAP map);
static int _new_map_set_stat (MAP map, struct map_node *n, int64_t val, int add);
/** @endcond */
#endif /* _MAP_H_ */
|
