1 #include <net-snmp/net-snmp-config.h>
2 
3 #include <string.h>
4 
5 #include <stdlib.h>
6 #include <sys/types.h>
7 
8 #include <net-snmp/net-snmp-features.h>
9 #include <net-snmp/net-snmp-includes.h>
10 
11 netsnmp_feature_child_of(oid_stash_all, libnetsnmp);
12 netsnmp_feature_child_of(oid_stash, oid_stash_all);
13 netsnmp_feature_child_of(oid_stash_no_free, oid_stash_all);
14 
15 #ifndef NETSNMP_FEATURE_REMOVE_OID_STASH
16 
17 /** @defgroup oid_stash Store and retrieve data referenced by an OID.
18     This is essentially a way of storing data associated with a given
19     OID.  It stores a bunch of data pointers within a memory tree that
20     allows fairly efficient lookups with a heavily populated tree.
21     @ingroup library
22     @{
23 */
24 
25 /*
26  * xxx-rks: when you have some spare time:
27  *
28  * b) basically, everything currently creates one node per sub-oid,
29  *    which is less than optimal. add code to create nodes with the
30  *    longest possible OID per node, and split nodes when necessary
31  *    during adds.
32  *
33  * c) If you are feeling really ambitious, also merge split nodes if
34  *    possible on a delete.
35  *
36  * xxx-wes: uh, right, like I *ever* have that much time.
37  *
38  */
39 
40 /***************************************************************************
41  *
42  *
43  ***************************************************************************/
44 
45 /**
46  * Create an netsnmp_oid_stash node
47  *
48  * @param mysize  the size of the child pointer array
49  *
50  * @return NULL on error, otherwise the newly allocated node
51  */
52 netsnmp_oid_stash_node *
netsnmp_oid_stash_create_sized_node(size_t mysize)53 netsnmp_oid_stash_create_sized_node(size_t mysize)
54 {
55     netsnmp_oid_stash_node *ret;
56     ret = SNMP_MALLOC_TYPEDEF(netsnmp_oid_stash_node);
57     if (!ret)
58         return NULL;
59     ret->children = (netsnmp_oid_stash_node**) calloc(mysize, sizeof(netsnmp_oid_stash_node *));
60     if (!ret->children) {
61         free(ret);
62         return NULL;
63     }
64     ret->children_size = mysize;
65     return ret;
66 }
67 
68 /** Creates a netsnmp_oid_stash_node.
69  * Assumes you want the default OID_STASH_CHILDREN_SIZE hash size for the node.
70  * @return NULL on error, otherwise the newly allocated node
71  */
72 NETSNMP_INLINE netsnmp_oid_stash_node *
netsnmp_oid_stash_create_node(void)73 netsnmp_oid_stash_create_node(void)
74 {
75     return netsnmp_oid_stash_create_sized_node(OID_STASH_CHILDREN_SIZE);
76 }
77 
78 netsnmp_feature_child_of(oid_stash_add_data, oid_stash_all);
79 #ifndef NETSNMP_FEATURE_REMOVE_OID_STASH_ADD_DATA
80 /** adds data to the stash at a given oid.
81 
82  * @param root the top of the stash tree
83  * @param lookup the oid index to store the data at.
84  * @param lookup_len the length of the lookup oid.
85  * @param mydata the data to store
86 
87  * @return SNMPERR_SUCCESS on success, SNMPERR_GENERR if data is
88    already there, SNMPERR_MALLOC on malloc failures or if arguments
89    passed in with NULL values.
90  */
91 int
netsnmp_oid_stash_add_data(netsnmp_oid_stash_node ** root,const oid * lookup,size_t lookup_len,void * mydata)92 netsnmp_oid_stash_add_data(netsnmp_oid_stash_node **root,
93                            const oid * lookup, size_t lookup_len, void *mydata)
94 {
95     netsnmp_oid_stash_node *curnode, *tmpp, *loopp;
96     unsigned int    i;
97 
98     if (!root || !lookup || lookup_len == 0)
99         return SNMPERR_GENERR;
100 
101     if (!*root) {
102         *root = netsnmp_oid_stash_create_node();
103         if (!*root)
104             return SNMPERR_MALLOC;
105     }
106     DEBUGMSGTL(( "oid_stash", "stash_add_data "));
107     DEBUGMSGOID(("oid_stash", lookup, lookup_len));
108     DEBUGMSG((   "oid_stash", "\n"));
109     tmpp = NULL;
110     for (curnode = *root, i = 0; i < lookup_len; i++) {
111         tmpp = curnode->children[lookup[i] % curnode->children_size];
112         if (!tmpp) {
113             /*
114              * no child in array at all
115              */
116             tmpp = curnode->children[lookup[i] % curnode->children_size] =
117                 netsnmp_oid_stash_create_node();
118             tmpp->value = lookup[i];
119             tmpp->parent = curnode;
120         } else {
121             for (loopp = tmpp; loopp; loopp = loopp->next_sibling) {
122                 if (loopp->value == lookup[i])
123                     break;
124             }
125             if (loopp) {
126                 tmpp = loopp;
127             } else {
128                 /*
129                  * none exists.  Create it
130                  */
131                 loopp = netsnmp_oid_stash_create_node();
132                 loopp->value = lookup[i];
133                 loopp->next_sibling = tmpp;
134                 loopp->parent = curnode;
135                 tmpp->prev_sibling = loopp;
136                 curnode->children[lookup[i] % curnode->children_size] =
137                     loopp;
138                 tmpp = loopp;
139             }
140             /*
141              * tmpp now points to the proper node
142              */
143         }
144         curnode = tmpp;
145     }
146     /*
147      * tmpp now points to the exact match
148      */
149     if (curnode->thedata)
150         return SNMPERR_GENERR;
151     if (NULL == tmpp)
152         return SNMPERR_GENERR;
153     tmpp->thedata = mydata;
154     return SNMPERR_SUCCESS;
155 }
156 #endif /* NETSNMP_FEATURE_REMOVE_OID_STASH_ADD_DATA */
157 
158 /** returns a node associated with a given OID.
159  * @param root the top of the stash tree
160  * @param lookup the oid to look up a node for.
161  * @param lookup_len the length of the lookup oid
162  */
163 netsnmp_oid_stash_node *
netsnmp_oid_stash_get_node(netsnmp_oid_stash_node * root,const oid * lookup,size_t lookup_len)164 netsnmp_oid_stash_get_node(netsnmp_oid_stash_node *root,
165                            const oid * lookup, size_t lookup_len)
166 {
167     netsnmp_oid_stash_node *curnode, *tmpp, *loopp;
168     unsigned int    i;
169 
170     if (!root)
171         return NULL;
172     tmpp = NULL;
173     for (curnode = root, i = 0; i < lookup_len; i++) {
174         tmpp = curnode->children[lookup[i] % curnode->children_size];
175         if (!tmpp) {
176             return NULL;
177         } else {
178             for (loopp = tmpp; loopp; loopp = loopp->next_sibling) {
179                 if (loopp->value == lookup[i])
180                     break;
181             }
182             if (loopp) {
183                 tmpp = loopp;
184             } else {
185                 return NULL;
186             }
187         }
188         curnode = tmpp;
189     }
190     return tmpp;
191 }
192 
193 /** returns the next node associated with a given OID. INCOMPLETE.
194     This is equivelent to a GETNEXT operation.
195  * @internal
196  * @param root the top of the stash tree
197  * @param lookup the oid to look up a node for.
198  * @param lookup_len the length of the lookup oid
199  */
200 netsnmp_feature_child_of(oid_stash_iterate, oid_stash_all);
201 #ifndef NETSNMP_FEATURE_REMOVE_OID_STASH_ITERATE
202 netsnmp_oid_stash_node *
netsnmp_oid_stash_getnext_node(netsnmp_oid_stash_node * root,oid * lookup,size_t lookup_len)203 netsnmp_oid_stash_getnext_node(netsnmp_oid_stash_node *root,
204                                oid * lookup, size_t lookup_len)
205 {
206     netsnmp_oid_stash_node *curnode, *tmpp, *loopp;
207     unsigned int    i, j, bigger_than = 0, do_bigger = 0;
208 
209     if (!root)
210         return NULL;
211     tmpp = NULL;
212 
213     /* get closest matching node */
214     for (curnode = root, i = 0; i < lookup_len; i++) {
215         tmpp = curnode->children[lookup[i] % curnode->children_size];
216         if (!tmpp) {
217             break;
218         } else {
219             for (loopp = tmpp; loopp; loopp = loopp->next_sibling) {
220                 if (loopp->value == lookup[i])
221                     break;
222             }
223             if (loopp) {
224                 tmpp = loopp;
225             } else {
226                 break;
227             }
228         }
229         curnode = tmpp;
230     }
231 
232     /* find the *next* node lexographically greater */
233     if (!curnode)
234         return NULL; /* ack! */
235 
236     if (i+1 < lookup_len) {
237         bigger_than = lookup[i+1];
238         do_bigger = 1;
239     }
240 
241     do {
242         /* check the children first */
243         tmpp = NULL;
244         /* next child must be (next) greater than our next search node */
245         /* XXX: should start this loop at best_nums[i]%... and wrap */
246         for(j = 0; j < curnode->children_size; j++) {
247             for (loopp = curnode->children[j];
248                  loopp; loopp = loopp->next_sibling) {
249                 if ((!do_bigger || loopp->value > bigger_than) &&
250                     (!tmpp || tmpp->value > loopp->value)) {
251                     tmpp = loopp;
252                     /* XXX: can do better and include min_nums[i] */
253                     if (tmpp->value <= curnode->children_size-1) {
254                         /* best we can do. */
255                         goto done_this_loop;
256                     }
257                 }
258             }
259         }
260 
261       done_this_loop:
262         if (tmpp && tmpp->thedata)
263             /* found a node with data.  Go with it. */
264             return tmpp;
265 
266         if (tmpp) {
267             /* found a child node without data, maybe find a grandchild? */
268             do_bigger = 0;
269             curnode = tmpp;
270         } else {
271             /* no respectable children (the bums), we'll have to go up.
272                But to do so, they must be better than our current best_num + 1.
273             */
274             do_bigger = 1;
275             bigger_than = curnode->value;
276             curnode = curnode->parent;
277         }
278     } while (curnode);
279 
280     /* fell off the top */
281     return NULL;
282 }
283 #endif /* NETSNMP_FEATURE_REMOVE_OID_STASH_ITERATE */
284 
285 netsnmp_feature_child_of(oid_stash_get_data, oid_stash_all);
286 #ifndef NETSNMP_FEATURE_REMOVE_OID_STASH_GET_DATA
287 /** returns a data pointer associated with a given OID.
288 
289     This is equivelent to netsnmp_oid_stash_get_node, but returns only
290     the data not the entire node.
291 
292  * @param root the top of the stash
293  * @param lookup the oid to search for
294  * @param lookup_len the length of the search oid.
295  */
296 void           *
netsnmp_oid_stash_get_data(netsnmp_oid_stash_node * root,const oid * lookup,size_t lookup_len)297 netsnmp_oid_stash_get_data(netsnmp_oid_stash_node *root,
298                            const oid * lookup, size_t lookup_len)
299 {
300     netsnmp_oid_stash_node *ret;
301     ret = netsnmp_oid_stash_get_node(root, lookup, lookup_len);
302     if (ret)
303         return ret->thedata;
304     return NULL;
305 }
306 #endif /* NETSNMP_FEATURE_REMOVE_OID_STASH_GET_DATA */
307 
308 netsnmp_feature_child_of(oid_stash_store_all, oid_stash_all);
309 #ifndef NETSNMP_FEATURE_REMOVE_OID_STASH_STORE_ALL
310 /** a wrapper around netsnmp_oid_stash_store for use with a snmp_alarm.
311  * when calling snmp_alarm, you can list this as a callback.  The
312  * clientarg should be a pointer to a netsnmp_oid_stash_save_info
313  * pointer.  It can also be called directly, of course.  The last
314  * argument (clientarg) is the only one that is used.  The rest are
315  * ignored by the function.
316  * @param majorID
317  * @param minorID
318  * @param serverarg
319  * @param clientarg A pointer to a netsnmp_oid_stash_save_info structure.
320  */
321 int
netsnmp_oid_stash_store_all(int majorID,int minorID,void * serverarg,void * clientarg)322 netsnmp_oid_stash_store_all(int majorID, int minorID,
323                             void *serverarg, void *clientarg) {
324     oid oidbase[MAX_OID_LEN];
325     netsnmp_oid_stash_save_info *sinfo;
326 
327     if (!clientarg)
328         return SNMP_ERR_NOERROR;
329 
330     sinfo = (netsnmp_oid_stash_save_info *) clientarg;
331     netsnmp_oid_stash_store(*(sinfo->root), sinfo->token, sinfo->dumpfn,
332                             oidbase,0);
333     return SNMP_ERR_NOERROR;
334 }
335 #endif /* NETSNMP_FEATURE_REMOVE_OID_STASH_STORE_ALL */
336 
337 /** stores data in a starsh tree to peristent storage.
338 
339     This function can be called to save all data in a stash tree to
340     Net-SNMP's percent storage.  Make sure you register a parsing
341     function with the read_config system to re-incorperate your saved
342     data into future trees.
343 
344     @param root the top of the stash to store.
345     @param tokenname the file token name to save in (passing "snmpd" will
346     save things into snmpd.conf).
347     @param dumpfn A function which can dump the data stored at a particular
348     node into a char buffer.
349     @param curoid must be a pointer to a OID array of length MAX_OID_LEN.
350     @param curoid_len must be 0 for the top level call.
351 */
352 void
netsnmp_oid_stash_store(netsnmp_oid_stash_node * root,const char * tokenname,NetSNMPStashDump * dumpfn,oid * curoid,size_t curoid_len)353 netsnmp_oid_stash_store(netsnmp_oid_stash_node *root,
354                         const char *tokenname, NetSNMPStashDump *dumpfn,
355                         oid *curoid, size_t curoid_len) {
356 
357     char buf[SNMP_MAXBUF];
358     netsnmp_oid_stash_node *tmpp;
359     char *cp;
360     char *appname = netsnmp_ds_get_string(NETSNMP_DS_LIBRARY_ID,
361                                           NETSNMP_DS_LIB_APPTYPE);
362     int i;
363 
364     if (!tokenname || !root || !curoid || !dumpfn)
365         return;
366 
367     for (i = 0; i < (int)root->children_size; i++) {
368         if (root->children[i]) {
369             for (tmpp = root->children[i]; tmpp; tmpp = tmpp->next_sibling) {
370                 curoid[curoid_len] = tmpp->value;
371                 if (tmpp->thedata) {
372                     snprintf(buf, sizeof(buf), "%s ", tokenname);
373                     cp = read_config_save_objid(buf+strlen(buf), curoid,
374                                                 curoid_len+1);
375                     *cp++ = ' ';
376                     *cp = '\0';
377                     if ((*dumpfn)(cp, sizeof(buf) - strlen(buf),
378                                   tmpp->thedata, tmpp))
379                         read_config_store(appname, buf);
380                 }
381                 netsnmp_oid_stash_store(tmpp, tokenname, dumpfn,
382                                         curoid, curoid_len+1);
383             }
384         }
385     }
386 }
387 
388 /** For debugging: dump the netsnmp_oid_stash tree to stdout
389     @param root The top of the tree
390     @param prefix a character string prefix printed to the beginning of each line.
391 */
392 void
oid_stash_dump(netsnmp_oid_stash_node * root,char * prefix)393 oid_stash_dump(netsnmp_oid_stash_node *root, char *prefix)
394 {
395     char            myprefix[MAX_OID_LEN * 4];
396     netsnmp_oid_stash_node *tmpp;
397     int             prefix_len = strlen(prefix) + 1;    /* actually it's +2 */
398     unsigned int    i;
399 
400     memset(myprefix, ' ', MAX_OID_LEN * 4);
401     myprefix[prefix_len] = '\0';
402 
403     for (i = 0; i < root->children_size; i++) {
404         if (root->children[i]) {
405             for (tmpp = root->children[i]; tmpp; tmpp = tmpp->next_sibling) {
406                 printf("%s%" NETSNMP_PRIo "d@%d: %s\n", prefix, tmpp->value, i,
407                        (tmpp->thedata) ? "DATA" : "");
408                 oid_stash_dump(tmpp, myprefix);
409             }
410         }
411     }
412 }
413 
414 /** Frees the contents of a netsnmp_oid_stash tree.
415     @param root the top of the tree (or branch to be freed)
416     @param freefn The function to be called on each data (void *)
417     pointer.  If left NULL the system free() function will be called
418 */
419 void
netsnmp_oid_stash_free(netsnmp_oid_stash_node ** root,NetSNMPStashFreeNode * freefn)420 netsnmp_oid_stash_free(netsnmp_oid_stash_node **root,
421                        NetSNMPStashFreeNode *freefn) {
422 
423     netsnmp_oid_stash_node *curnode, *tmpp;
424     unsigned int    i;
425 
426     if (!root || !*root)
427         return;
428 
429     /* loop through all our children and free each node */
430     for (i = 0; i < (*root)->children_size; i++) {
431         if ((*root)->children[i]) {
432             for(tmpp = (*root)->children[i]; tmpp; tmpp = curnode) {
433                 if (tmpp->thedata) {
434                     if (freefn)
435                         (*freefn)(tmpp->thedata);
436                     else
437                         free(tmpp->thedata);
438                 }
439                 curnode = tmpp->next_sibling;
440                 netsnmp_oid_stash_free(&tmpp, freefn);
441             }
442         }
443     }
444     free((*root)->children);
445     free (*root);
446     *root = NULL;
447 }
448 
449 #else /* NETSNMP_FEATURE_REMOVE_OID_STASH */
450 netsnmp_feature_unused(oid_stash);
451 #endif/* NETSNMP_FEATURE_REMOVE_OID_STASH */
452 
453 #ifndef NETSNMP_FEATURE_REMOVE_OID_STASH_NO_FREE
454 void
netsnmp_oid_stash_no_free(void * bogus)455 netsnmp_oid_stash_no_free(void *bogus)
456 {
457     /* noop */
458 }
459 #endif /* NETSNMP_FEATURE_REMOVE_OID_STASH_NO_FREE */
460 
461 /** @} */
462