First run at integrating LWIP into the tree (again)
[akaros.git] / user / lwip / core / snmp / mib_structs.c
1 /**
2  * @file
3  * MIB tree access/construction functions.
4  */
5
6 /*
7  * Copyright (c) 2006 Axon Digital Design B.V., The Netherlands.
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without modification,
11  * are permitted provided that the following conditions are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright notice,
14  *    this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright notice,
16  *    this list of conditions and the following disclaimer in the documentation
17  *    and/or other materials provided with the distribution.
18  * 3. The name of the author may not be used to endorse or promote products
19  *    derived from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
22  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
23  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
24  * SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
26  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
29  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
30  * OF SUCH DAMAGE.
31  *
32  * Author: Christiaan Simons <christiaan.simons@axon.tv>
33  */
34
35 #include "lwip/opt.h"
36
37 #if LWIP_SNMP /* don't build if not configured for use in lwipopts.h */
38
39 #include "lwip/snmp_structs.h"
40 #include "lwip/mem.h"
41
42 /** .iso.org.dod.internet address prefix, @see snmp_iso_*() */
43 const s32_t prefix[4] = {1, 3, 6, 1};
44
45 #define NODE_STACK_SIZE (LWIP_SNMP_OBJ_ID_LEN)
46 /** node stack entry (old news?) */
47 struct nse
48 {
49   /** right child */
50   struct mib_node* r_ptr;
51   /** right child identifier */
52   s32_t r_id;
53   /** right child next level */
54   u8_t r_nl;
55 };
56 static u8_t node_stack_cnt;
57 static struct nse node_stack[NODE_STACK_SIZE];
58
59 /**
60  * Pushes nse struct onto stack.
61  */
62 static void
63 push_node(struct nse* node)
64 {
65   LWIP_ASSERT("node_stack_cnt < NODE_STACK_SIZE",node_stack_cnt < NODE_STACK_SIZE);
66   LWIP_DEBUGF(SNMP_MIB_DEBUG,("push_node() node=%p id=%"S32_F"\n",(void*)(node->r_ptr),node->r_id));
67   if (node_stack_cnt < NODE_STACK_SIZE)
68   {
69     node_stack[node_stack_cnt] = *node;
70     node_stack_cnt++;
71   }
72 }
73
74 /**
75  * Pops nse struct from stack.
76  */
77 static void
78 pop_node(struct nse* node)
79 {
80   if (node_stack_cnt > 0)
81   {
82     node_stack_cnt--;
83     *node = node_stack[node_stack_cnt];
84   }
85   LWIP_DEBUGF(SNMP_MIB_DEBUG,("pop_node() node=%p id=%"S32_F"\n",(void *)(node->r_ptr),node->r_id));
86 }
87
88 /**
89  * Conversion from ifIndex to lwIP netif
90  * @param ifindex is a s32_t object sub-identifier
91  * @param netif points to returned netif struct pointer
92  */
93 void
94 snmp_ifindextonetif(s32_t ifindex, struct netif **netif)
95 {
96   struct netif *nif = netif_list;
97   u16_t i, ifidx;
98
99   ifidx = ifindex - 1;
100   i = 0;
101   while ((nif != NULL) && (i < ifidx))
102   {
103     nif = nif->next;
104     i++;
105   }
106   *netif = nif;
107 }
108
109 /**
110  * Conversion from lwIP netif to ifIndex
111  * @param netif points to a netif struct
112  * @param ifidx points to s32_t object sub-identifier
113  */
114 void
115 snmp_netiftoifindex(struct netif *netif, s32_t *ifidx)
116 {
117   struct netif *nif = netif_list;
118   u16_t i;
119
120   i = 0;
121   while ((nif != NULL) && (nif != netif))
122   {
123     nif = nif->next;
124     i++;
125   }
126   *ifidx = i+1;
127 }
128
129 /**
130  * Conversion from oid to lwIP ip_addr
131  * @param ident points to s32_t ident[4] input
132  * @param ip points to output struct
133  */
134 void
135 snmp_oidtoip(s32_t *ident, struct ip_addr *ip)
136 {
137   u32_t ipa;
138
139   ipa = ident[0];
140   ipa <<= 8;
141   ipa |= ident[1];
142   ipa <<= 8;
143   ipa |= ident[2];
144   ipa <<= 8;
145   ipa |= ident[3];
146   ip->addr = ipa;
147 }
148
149 /**
150  * Conversion from lwIP ip_addr to oid
151  * @param ip points to input struct
152  * @param ident points to s32_t ident[4] output
153  */
154 void
155 snmp_iptooid(struct ip_addr *ip, s32_t *ident)
156 {
157   u32_t ipa;
158
159   ipa = ip->addr;
160   ident[0] = (ipa >> 24) & 0xff;
161   ident[1] = (ipa >> 16) & 0xff;
162   ident[2] = (ipa >> 8) & 0xff;
163   ident[3] = ipa & 0xff;
164 }
165
166 struct mib_list_node *
167 snmp_mib_ln_alloc(s32_t id)
168 {
169   struct mib_list_node *ln;
170
171   ln = (struct mib_list_node *)mem_malloc(sizeof(struct mib_list_node));
172   if (ln != NULL)
173   {
174     ln->prev = NULL;
175     ln->next = NULL;
176     ln->objid = id;
177     ln->nptr = NULL;
178   }
179   return ln;
180 }
181
182 void
183 snmp_mib_ln_free(struct mib_list_node *ln)
184 {
185   mem_free(ln);
186 }
187
188 struct mib_list_rootnode *
189 snmp_mib_lrn_alloc(void)
190 {
191   struct mib_list_rootnode *lrn;
192
193   lrn = (struct mib_list_rootnode*)mem_malloc(sizeof(struct mib_list_rootnode));
194   if (lrn != NULL)
195   {
196     lrn->get_object_def = noleafs_get_object_def;
197     lrn->get_value = noleafs_get_value;
198     lrn->set_test = noleafs_set_test;
199     lrn->set_value = noleafs_set_value;
200     lrn->node_type = MIB_NODE_LR;
201     lrn->maxlength = 0;
202     lrn->head = NULL;
203     lrn->tail = NULL;
204     lrn->count = 0;
205   }
206   return lrn;
207 }
208
209 void
210 snmp_mib_lrn_free(struct mib_list_rootnode *lrn)
211 {
212   mem_free(lrn);
213 }
214
215 /**
216  * Inserts node in idx list in a sorted
217  * (ascending order) fashion and
218  * allocates the node if needed.
219  *
220  * @param rn points to the root node
221  * @param objid is the object sub identifier
222  * @param insn points to a pointer to the inserted node
223  *   used for constructing the tree.
224  * @return -1 if failed, 1 if inserted, 2 if present.
225  */
226 s8_t
227 snmp_mib_node_insert(struct mib_list_rootnode *rn, s32_t objid, struct mib_list_node **insn)
228 {
229   struct mib_list_node *nn;
230   s8_t insert;
231
232   LWIP_ASSERT("rn != NULL",rn != NULL);
233
234   /* -1 = malloc failure, 0 = not inserted, 1 = inserted, 2 = was present */
235   insert = 0;
236   if (rn->head == NULL)
237   {
238     /* empty list, add first node */
239     LWIP_DEBUGF(SNMP_MIB_DEBUG,("alloc empty list objid==%"S32_F"\n",objid));
240     nn = snmp_mib_ln_alloc(objid);
241     if (nn != NULL)
242     {
243       rn->head = nn;
244       rn->tail = nn;
245       *insn = nn;
246       insert = 1;
247     }
248     else
249     {
250       insert = -1;
251     }
252   }
253   else
254   {
255     struct mib_list_node *n;
256     /* at least one node is present */
257     n = rn->head;
258     while ((n != NULL) && (insert == 0))
259     {
260       if (n->objid == objid)
261       {
262         /* node is already there */
263         LWIP_DEBUGF(SNMP_MIB_DEBUG,("node already there objid==%"S32_F"\n",objid));
264         *insn = n;
265         insert = 2;
266       }
267       else if (n->objid < objid)
268       {
269         if (n->next == NULL)
270         {
271           /* alloc and insert at the tail */
272           LWIP_DEBUGF(SNMP_MIB_DEBUG,("alloc ins tail objid==%"S32_F"\n",objid));
273           nn = snmp_mib_ln_alloc(objid);
274           if (nn != NULL)
275           {
276             nn->next = NULL;
277             nn->prev = n;
278             n->next = nn;
279             rn->tail = nn;
280             *insn = nn;
281             insert = 1;
282           }
283           else
284           {
285             /* insertion failure */
286             insert = -1;
287           }
288         }
289         else
290         {
291           /* there's more to explore: traverse list */
292           LWIP_DEBUGF(SNMP_MIB_DEBUG,("traverse list\n"));
293           n = n->next;
294         }
295       }
296       else
297       {
298         /* n->objid > objid */
299         /* alloc and insert between n->prev and n */
300         LWIP_DEBUGF(SNMP_MIB_DEBUG,("alloc ins n->prev, objid==%"S32_F", n\n",objid));
301         nn = snmp_mib_ln_alloc(objid);
302         if (nn != NULL)
303         {
304           if (n->prev == NULL)
305           {
306             /* insert at the head */
307             nn->next = n;
308             nn->prev = NULL;
309             rn->head = nn;
310             n->prev = nn;
311           }
312           else
313           {
314             /* insert in the middle */
315             nn->next = n;
316             nn->prev = n->prev;
317             n->prev->next = nn;
318             n->prev = nn;
319           }
320           *insn = nn;
321           insert = 1;
322         }
323         else
324         {
325           /* insertion failure */
326           insert = -1;
327         }
328       }
329     }
330   }
331   if (insert == 1)
332   {
333     rn->count += 1;
334   }
335   LWIP_ASSERT("insert != 0",insert != 0);
336   return insert;
337 }
338
339 /**
340  * Finds node in idx list and returns deletion mark.
341  *
342  * @param rn points to the root node
343  * @param objid  is the object sub identifier
344  * @param fn returns pointer to found node
345  * @return 0 if not found, 1 if deletable,
346  *   2 can't delete (2 or more children), 3 not a list_node
347  */
348 s8_t
349 snmp_mib_node_find(struct mib_list_rootnode *rn, s32_t objid, struct mib_list_node **fn)
350 {
351   s8_t fc;
352   struct mib_list_node *n;
353
354   LWIP_ASSERT("rn != NULL",rn != NULL);
355   n = rn->head;
356   while ((n != NULL) && (n->objid != objid))
357   {
358     n = n->next;
359   }
360   if (n == NULL)
361   {
362     fc = 0;
363   }
364   else if (n->nptr == NULL)
365   {
366     /* leaf, can delete node */
367     fc = 1;
368   }
369   else
370   {
371     struct mib_list_rootnode *r;
372
373     if (n->nptr->node_type == MIB_NODE_LR)
374     {
375       r = (struct mib_list_rootnode *)n->nptr;
376       if (r->count > 1)
377       {
378         /* can't delete node */
379         fc = 2;
380       }
381       else
382       {
383         /* count <= 1, can delete node */
384         fc = 1;
385       }
386     }
387     else
388     {
389       /* other node type */
390       fc = 3;
391     }
392   }
393   *fn = n;
394   return fc;
395 }
396
397 /**
398  * Removes node from idx list
399  * if it has a single child left.
400  *
401  * @param rn points to the root node
402  * @param n points to the node to delete
403  * @return the nptr to be freed by caller
404  */
405 struct mib_list_rootnode *
406 snmp_mib_node_delete(struct mib_list_rootnode *rn, struct mib_list_node *n)
407 {
408   struct mib_list_rootnode *next;
409
410   LWIP_ASSERT("rn != NULL",rn != NULL);
411   LWIP_ASSERT("n != NULL",n != NULL);
412
413   /* caller must remove this sub-tree */
414   next = (struct mib_list_rootnode*)(n->nptr);
415   rn->count -= 1;
416
417   if (n == rn->head)
418   {
419     rn->head = n->next;
420     if (n->next != NULL)
421     {
422       /* not last node, new list begin */
423       n->next->prev = NULL;
424     }
425   }
426   else if (n == rn->tail)
427   {
428     rn->tail = n->prev;
429     if (n->prev != NULL)
430     {
431       /* not last node, new list end */
432       n->prev->next = NULL;
433     }
434   }
435   else
436   {
437     /* node must be in the middle */
438     n->prev->next = n->next;
439     n->next->prev = n->prev;
440   }
441   LWIP_DEBUGF(SNMP_MIB_DEBUG,("free list objid==%"S32_F"\n",n->objid));
442   snmp_mib_ln_free(n);
443   if (rn->count == 0)
444   {
445     rn->head = NULL;
446     rn->tail = NULL;
447   }
448   return next;
449 }
450
451
452
453 /**
454  * Searches tree for the supplied (scalar?) object identifier.
455  *
456  * @param node points to the root of the tree ('.internet')
457  * @param ident_len the length of the supplied object identifier
458  * @param ident points to the array of sub identifiers
459  * @param np points to the found object instance (rerurn)
460  * @return pointer to the requested parent (!) node if success, NULL otherwise
461  */
462 struct mib_node *
463 snmp_search_tree(struct mib_node *node, u8_t ident_len, s32_t *ident, struct snmp_name_ptr *np)
464 {
465   u8_t node_type, ext_level;
466
467   ext_level = 0;
468   LWIP_DEBUGF(SNMP_MIB_DEBUG,("node==%p *ident==%"S32_F"\n",(void*)node,*ident));
469   while (node != NULL)
470   {
471     node_type = node->node_type;
472     if ((node_type == MIB_NODE_AR) || (node_type == MIB_NODE_RA))
473     {
474       struct mib_array_node *an;
475       u16_t i;
476
477       if (ident_len > 0)
478       {
479         /* array node (internal ROM or RAM, fixed length) */
480         an = (struct mib_array_node *)node;
481         i = 0;
482         while ((i < an->maxlength) && (an->objid[i] != *ident))
483         {
484           i++;
485         }
486         if (i < an->maxlength)
487         {
488           /* found it, if available proceed to child, otherwise inspect leaf */
489           LWIP_DEBUGF(SNMP_MIB_DEBUG,("an->objid[%"U16_F"]==%"S32_F" *ident==%"S32_F"\n",i,an->objid[i],*ident));
490           if (an->nptr[i] == NULL)
491           {
492             /* a scalar leaf OR table,
493                inspect remaining instance number / table index */
494             np->ident_len = ident_len;
495             np->ident = ident;
496             return (struct mib_node*)an;
497           }
498           else
499           {
500             /* follow next child pointer */
501             ident++;
502             ident_len--;
503             node = an->nptr[i];
504           }
505         }
506         else
507         {
508           /* search failed, identifier mismatch (nosuchname) */
509           LWIP_DEBUGF(SNMP_MIB_DEBUG,("an search failed *ident==%"S32_F"\n",*ident));
510           return NULL;
511         }
512       }
513       else
514       {
515         /* search failed, short object identifier (nosuchname) */
516         LWIP_DEBUGF(SNMP_MIB_DEBUG,("an search failed, short object identifier\n"));
517         return NULL;
518       }
519     }
520     else if(node_type == MIB_NODE_LR)
521     {
522       struct mib_list_rootnode *lrn;
523       struct mib_list_node *ln;
524
525       if (ident_len > 0)
526       {
527         /* list root node (internal 'RAM', variable length) */
528         lrn = (struct mib_list_rootnode *)node;
529         ln = lrn->head;
530         /* iterate over list, head to tail */
531         while ((ln != NULL) && (ln->objid != *ident))
532         {
533           ln = ln->next;
534         }
535         if (ln != NULL)
536         {
537           /* found it, proceed to child */;
538           LWIP_DEBUGF(SNMP_MIB_DEBUG,("ln->objid==%"S32_F" *ident==%"S32_F"\n",ln->objid,*ident));
539           if (ln->nptr == NULL)
540           {
541             np->ident_len = ident_len;
542             np->ident = ident;
543             return (struct mib_node*)lrn;
544           }
545           else
546           {
547             /* follow next child pointer */
548             ident_len--;
549             ident++;
550             node = ln->nptr;
551           }
552         }
553         else
554         {
555           /* search failed */
556           LWIP_DEBUGF(SNMP_MIB_DEBUG,("ln search failed *ident==%"S32_F"\n",*ident));
557           return NULL;
558         }
559       }
560       else
561       {
562         /* search failed, short object identifier (nosuchname) */
563         LWIP_DEBUGF(SNMP_MIB_DEBUG,("ln search failed, short object identifier\n"));
564         return NULL;
565       }
566     }
567     else if(node_type == MIB_NODE_EX)
568     {
569       struct mib_external_node *en;
570       u16_t i, len;
571
572       if (ident_len > 0)
573       {
574         /* external node (addressing and access via functions) */
575         en = (struct mib_external_node *)node;
576
577         i = 0;
578         len = en->level_length(en->addr_inf,ext_level);
579         while ((i < len) && (en->ident_cmp(en->addr_inf,ext_level,i,*ident) != 0))
580         {
581           i++;
582         }
583         if (i < len)
584         {
585           s32_t debug_id;
586
587           en->get_objid(en->addr_inf,ext_level,i,&debug_id);
588           LWIP_DEBUGF(SNMP_MIB_DEBUG,("en->objid==%"S32_F" *ident==%"S32_F"\n",debug_id,*ident));
589           if ((ext_level + 1) == en->tree_levels)
590           {
591             np->ident_len = ident_len;
592             np->ident = ident;
593             return (struct mib_node*)en;
594           }
595           else
596           {
597             /* found it, proceed to child */
598             ident_len--;
599             ident++;
600             ext_level++;
601           }
602         }
603         else
604         {
605           /* search failed */
606           LWIP_DEBUGF(SNMP_MIB_DEBUG,("en search failed *ident==%"S32_F"\n",*ident));
607           return NULL;
608         }
609       }
610       else
611       {
612         /* search failed, short object identifier (nosuchname) */
613         LWIP_DEBUGF(SNMP_MIB_DEBUG,("en search failed, short object identifier\n"));
614         return NULL;
615       }
616     }
617     else if (node_type == MIB_NODE_SC)
618     {
619       mib_scalar_node *sn;
620
621       sn = (mib_scalar_node *)node;
622       if ((ident_len == 1) && (*ident == 0))
623       {
624         np->ident_len = ident_len;
625         np->ident = ident;
626         return (struct mib_node*)sn;
627       }
628       else
629       {
630         /* search failed, short object identifier (nosuchname) */
631         LWIP_DEBUGF(SNMP_MIB_DEBUG,("search failed, invalid object identifier length\n"));
632         return NULL;
633       }
634     }
635     else
636     {
637       /* unknown node_type */
638       LWIP_DEBUGF(SNMP_MIB_DEBUG,("search failed node_type %"U16_F" unkown\n",(u16_t)node_type));
639       return NULL;
640     }
641   }
642   /* done, found nothing */
643   LWIP_DEBUGF(SNMP_MIB_DEBUG,("search failed node==%p\n",(void*)node));
644   return NULL;
645 }
646
647 /**
648  * Test table for presence of at least one table entry.
649  */
650 static u8_t
651 empty_table(struct mib_node *node)
652 {
653   u8_t node_type;
654   u8_t empty = 0;
655
656   if (node != NULL)
657   {
658     node_type = node->node_type;
659     if (node_type == MIB_NODE_LR)
660     {
661       struct mib_list_rootnode *lrn;
662       lrn = (struct mib_list_rootnode *)node;
663       if ((lrn->count == 0) || (lrn->head == NULL))
664       {
665         empty = 1;
666       }
667     }
668     else if ((node_type == MIB_NODE_AR) || (node_type == MIB_NODE_RA))
669     {
670       struct mib_array_node *an;
671       an = (struct mib_array_node *)node;
672       if ((an->maxlength == 0) || (an->nptr == NULL))
673       {
674         empty = 1;
675       }
676     }
677     else if (node_type == MIB_NODE_EX)
678     {
679       struct mib_external_node *en;
680       en = (struct mib_external_node *)node;
681       if (en->tree_levels == 0)
682       {
683         empty = 1;
684       }
685     }
686   }
687   return empty;
688 }
689
690 /**
691  * Tree expansion.
692  */
693 struct mib_node *
694 snmp_expand_tree(struct mib_node *node, u8_t ident_len, s32_t *ident, struct snmp_obj_id *oidret)
695 {
696   u8_t node_type, ext_level, climb_tree;
697
698   ext_level = 0;
699   /* reset node stack */
700   node_stack_cnt = 0;
701   while (node != NULL)
702   {
703     climb_tree = 0;
704     node_type = node->node_type;
705     if ((node_type == MIB_NODE_AR) || (node_type == MIB_NODE_RA))
706     {
707       struct mib_array_node *an;
708       u16_t i;
709
710       /* array node (internal ROM or RAM, fixed length) */
711       an = (struct mib_array_node *)node;
712       if (ident_len > 0)
713       {
714         i = 0;
715         while ((i < an->maxlength) && (an->objid[i] < *ident))
716         {
717           i++;
718         }
719         if (i < an->maxlength)
720         {
721           LWIP_DEBUGF(SNMP_MIB_DEBUG,("an->objid[%"U16_F"]==%"S32_F" *ident==%"S32_F"\n",i,an->objid[i],*ident));
722           /* add identifier to oidret */
723           oidret->id[oidret->len] = an->objid[i];
724           (oidret->len)++;
725
726           if (an->nptr[i] == NULL)
727           {
728             LWIP_DEBUGF(SNMP_MIB_DEBUG,("leaf node\n"));
729             /* leaf node (e.g. in a fixed size table) */
730             if (an->objid[i] > *ident)
731             {
732               return (struct mib_node*)an;
733             }
734             else if ((i + 1) < an->maxlength)
735             {
736               /* an->objid[i] == *ident */
737               (oidret->len)--;
738               oidret->id[oidret->len] = an->objid[i + 1];
739               (oidret->len)++;
740               return (struct mib_node*)an;
741             }
742             else
743             {
744               /* (i + 1) == an->maxlength */
745               (oidret->len)--;
746               climb_tree = 1;
747             }
748           }
749           else
750           {
751             u8_t j;
752             struct nse cur_node;
753
754             LWIP_DEBUGF(SNMP_MIB_DEBUG,("non-leaf node\n"));
755             /* non-leaf, store right child ptr and id */
756             j = i + 1;
757             while ((j < an->maxlength) && (empty_table(an->nptr[j])))
758             {
759               j++;
760             }
761             if (j < an->maxlength)
762             {
763               cur_node.r_ptr = an->nptr[j];
764               cur_node.r_id = an->objid[j];
765               cur_node.r_nl = 0;
766             }
767             else
768             {
769               cur_node.r_ptr = NULL;
770             }
771             push_node(&cur_node);
772             if (an->objid[i] == *ident)
773             {
774               ident_len--;
775               ident++;
776             }
777             else
778             {
779               /* an->objid[i] < *ident */
780               ident_len = 0;
781             }
782             /* follow next child pointer */
783             node = an->nptr[i];
784           }
785         }
786         else
787         {
788           /* i == an->maxlength */
789           climb_tree = 1;
790         }
791       }
792       else
793       {
794         u8_t j;
795         /* ident_len == 0, complete with leftmost '.thing' */
796         j = 0;
797         while ((j < an->maxlength) && empty_table(an->nptr[j]))
798         {
799           j++;
800         }
801         if (j < an->maxlength)
802         {
803           LWIP_DEBUGF(SNMP_MIB_DEBUG,("left an->objid[j]==%"S32_F"\n",an->objid[j]));
804           oidret->id[oidret->len] = an->objid[j];
805           (oidret->len)++;
806           if (an->nptr[j] == NULL)
807           {
808             /* leaf node */
809             return (struct mib_node*)an;
810           }
811           else
812           {
813             /* no leaf, continue */
814             node = an->nptr[j];
815           }
816         }
817         else
818         {
819           /* j == an->maxlength */
820           climb_tree = 1;
821         }
822       }
823     }
824     else if(node_type == MIB_NODE_LR)
825     {
826       struct mib_list_rootnode *lrn;
827       struct mib_list_node *ln;
828
829       /* list root node (internal 'RAM', variable length) */
830       lrn = (struct mib_list_rootnode *)node;
831       if (ident_len > 0)
832       {
833         ln = lrn->head;
834         /* iterate over list, head to tail */
835         while ((ln != NULL) && (ln->objid < *ident))
836         {
837           ln = ln->next;
838         }
839         if (ln != NULL)
840         {
841           LWIP_DEBUGF(SNMP_MIB_DEBUG,("ln->objid==%"S32_F" *ident==%"S32_F"\n",ln->objid,*ident));
842           oidret->id[oidret->len] = ln->objid;
843           (oidret->len)++;
844           if (ln->nptr == NULL)
845           {
846             /* leaf node */
847             if (ln->objid > *ident)
848             {
849               return (struct mib_node*)lrn;
850             }
851             else if (ln->next != NULL)
852             {
853               /* ln->objid == *ident */
854               (oidret->len)--;
855               oidret->id[oidret->len] = ln->next->objid;
856               (oidret->len)++;
857               return (struct mib_node*)lrn;
858             }
859             else
860             {
861               /* ln->next == NULL */
862               (oidret->len)--;
863               climb_tree = 1;
864             }
865           }
866           else
867           {
868             struct mib_list_node *jn;
869             struct nse cur_node;
870
871             /* non-leaf, store right child ptr and id */
872             jn = ln->next;
873             while ((jn != NULL) && empty_table(jn->nptr))
874             {
875               jn = jn->next;
876             }
877             if (jn != NULL)
878             {
879               cur_node.r_ptr = jn->nptr;
880               cur_node.r_id = jn->objid;
881               cur_node.r_nl = 0;
882             }
883             else
884             {
885               cur_node.r_ptr = NULL;
886             }
887             push_node(&cur_node);
888             if (ln->objid == *ident)
889             {
890               ident_len--;
891               ident++;
892             }
893             else
894             {
895               /* ln->objid < *ident */
896               ident_len = 0;
897             }
898             /* follow next child pointer */
899             node = ln->nptr;
900           }
901
902         }
903         else
904         {
905           /* ln == NULL */
906           climb_tree = 1;
907         }
908       }
909       else
910       {
911         struct mib_list_node *jn;
912         /* ident_len == 0, complete with leftmost '.thing' */
913         jn = lrn->head;
914         while ((jn != NULL) && empty_table(jn->nptr))
915         {
916           jn = jn->next;
917         }
918         if (jn != NULL)
919         {
920           LWIP_DEBUGF(SNMP_MIB_DEBUG,("left jn->objid==%"S32_F"\n",jn->objid));
921           oidret->id[oidret->len] = jn->objid;
922           (oidret->len)++;
923           if (jn->nptr == NULL)
924           {
925             /* leaf node */
926             LWIP_DEBUGF(SNMP_MIB_DEBUG,("jn->nptr == NULL\n"));
927             return (struct mib_node*)lrn;
928           }
929           else
930           {
931             /* no leaf, continue */
932             node = jn->nptr;
933           }
934         }
935         else
936         {
937           /* jn == NULL */
938           climb_tree = 1;
939         }
940       }
941     }
942     else if(node_type == MIB_NODE_EX)
943     {
944       struct mib_external_node *en;
945       s32_t ex_id;
946
947       /* external node (addressing and access via functions) */
948       en = (struct mib_external_node *)node;
949       if (ident_len > 0)
950       {
951         u16_t i, len;
952
953         i = 0;
954         len = en->level_length(en->addr_inf,ext_level);
955         while ((i < len) && (en->ident_cmp(en->addr_inf,ext_level,i,*ident) < 0))
956         {
957           i++;
958         }
959         if (i < len)
960         {
961           /* add identifier to oidret */
962           en->get_objid(en->addr_inf,ext_level,i,&ex_id);
963           LWIP_DEBUGF(SNMP_MIB_DEBUG,("en->objid[%"U16_F"]==%"S32_F" *ident==%"S32_F"\n",i,ex_id,*ident));
964           oidret->id[oidret->len] = ex_id;
965           (oidret->len)++;
966
967           if ((ext_level + 1) == en->tree_levels)
968           {
969             LWIP_DEBUGF(SNMP_MIB_DEBUG,("leaf node\n"));
970             /* leaf node */
971             if (ex_id > *ident)
972             {
973               return (struct mib_node*)en;
974             }
975             else if ((i + 1) < len)
976             {
977               /* ex_id == *ident */
978               en->get_objid(en->addr_inf,ext_level,i + 1,&ex_id);
979               (oidret->len)--;
980               oidret->id[oidret->len] = ex_id;
981               (oidret->len)++;
982               return (struct mib_node*)en;
983             }
984             else
985             {
986               /* (i + 1) == len */
987               (oidret->len)--;
988               climb_tree = 1;
989             }
990           }
991           else
992           {
993             u8_t j;
994             struct nse cur_node;
995
996             LWIP_DEBUGF(SNMP_MIB_DEBUG,("non-leaf node\n"));
997             /* non-leaf, store right child ptr and id */
998             j = i + 1;
999             if (j < len)
1000             {
1001               /* right node is the current external node */
1002               cur_node.r_ptr = node;
1003               en->get_objid(en->addr_inf,ext_level,j,&cur_node.r_id);
1004               cur_node.r_nl = ext_level + 1;
1005             }
1006             else
1007             {
1008               cur_node.r_ptr = NULL;
1009             }
1010             push_node(&cur_node);
1011             if (en->ident_cmp(en->addr_inf,ext_level,i,*ident) == 0)
1012             {
1013               ident_len--;
1014               ident++;
1015             }
1016             else
1017             {
1018               /* external id < *ident */
1019               ident_len = 0;
1020             }
1021             /* proceed to child */
1022             ext_level++;
1023           }
1024         }
1025         else
1026         {
1027           /* i == len (en->level_len()) */
1028           climb_tree = 1;
1029         }
1030       }
1031       else
1032       {
1033         /* ident_len == 0, complete with leftmost '.thing' */
1034         en->get_objid(en->addr_inf,ext_level,0,&ex_id);
1035         LWIP_DEBUGF(SNMP_MIB_DEBUG,("left en->objid==%"S32_F"\n",ex_id));
1036         oidret->id[oidret->len] = ex_id;
1037         (oidret->len)++;
1038         if ((ext_level + 1) == en->tree_levels)
1039         {
1040           /* leaf node */
1041           LWIP_DEBUGF(SNMP_MIB_DEBUG,("(ext_level + 1) == en->tree_levels\n"));
1042           return (struct mib_node*)en;
1043         }
1044         else
1045         {
1046           /* no leaf, proceed to child */
1047           ext_level++;
1048         }
1049       }
1050     }
1051     else if(node_type == MIB_NODE_SC)
1052     {
1053       mib_scalar_node *sn;
1054
1055       /* scalar node  */
1056       sn = (mib_scalar_node *)node;
1057       if (ident_len > 0)
1058       {
1059         /* at .0 */
1060         climb_tree = 1;
1061       }
1062       else
1063       {
1064         /* ident_len == 0, complete object identifier */
1065         oidret->id[oidret->len] = 0;
1066         (oidret->len)++;
1067         /* leaf node */
1068         LWIP_DEBUGF(SNMP_MIB_DEBUG,("completed scalar leaf\n"));
1069         return (struct mib_node*)sn;
1070       }
1071     }
1072     else
1073     {
1074       /* unknown/unhandled node_type */
1075       LWIP_DEBUGF(SNMP_MIB_DEBUG,("expand failed node_type %"U16_F" unkown\n",(u16_t)node_type));
1076       return NULL;
1077     }
1078
1079     if (climb_tree)
1080     {
1081       struct nse child;
1082
1083       /* find right child ptr */
1084       child.r_ptr = NULL;
1085       child.r_id = 0;
1086       child.r_nl = 0;
1087       while ((node_stack_cnt > 0) && (child.r_ptr == NULL))
1088       {
1089         pop_node(&child);
1090         /* trim returned oid */
1091         (oidret->len)--;
1092       }
1093       if (child.r_ptr != NULL)
1094       {
1095         /* incoming ident is useless beyond this point */
1096         ident_len = 0;
1097         oidret->id[oidret->len] = child.r_id;
1098         oidret->len++;
1099         node = child.r_ptr;
1100         ext_level = child.r_nl;
1101       }
1102       else
1103       {
1104         /* tree ends here ... */
1105         LWIP_DEBUGF(SNMP_MIB_DEBUG,("expand failed, tree ends here\n"));
1106         return NULL;
1107       }
1108     }
1109   }
1110   /* done, found nothing */
1111   LWIP_DEBUGF(SNMP_MIB_DEBUG,("expand failed node==%p\n",(void*)node));
1112   return NULL;
1113 }
1114
1115 /**
1116  * Test object identifier for the iso.org.dod.internet prefix.
1117  *
1118  * @param ident_len the length of the supplied object identifier
1119  * @param ident points to the array of sub identifiers
1120  * @return 1 if it matches, 0 otherwise
1121  */
1122 u8_t
1123 snmp_iso_prefix_tst(u8_t ident_len, s32_t *ident)
1124 {
1125   if ((ident_len > 3) &&
1126       (ident[0] == 1) && (ident[1] == 3) &&
1127       (ident[2] == 6) && (ident[3] == 1))
1128   {
1129     return 1;
1130   }
1131   else
1132   {
1133     return 0;
1134   }
1135 }
1136
1137 /**
1138  * Expands object identifier to the iso.org.dod.internet
1139  * prefix for use in getnext operation.
1140  *
1141  * @param ident_len the length of the supplied object identifier
1142  * @param ident points to the array of sub identifiers
1143  * @param oidret points to returned expanded object identifier
1144  * @return 1 if it matches, 0 otherwise
1145  *
1146  * @note ident_len 0 is allowed, expanding to the first known object id!!
1147  */
1148 u8_t
1149 snmp_iso_prefix_expand(u8_t ident_len, s32_t *ident, struct snmp_obj_id *oidret)
1150 {
1151   const s32_t *prefix_ptr;
1152   s32_t *ret_ptr;
1153   u8_t i;
1154
1155   i = 0;
1156   prefix_ptr = &prefix[0];
1157   ret_ptr = &oidret->id[0];
1158   ident_len = ((ident_len < 4)?ident_len:4);
1159   while ((i < ident_len) && ((*ident) <= (*prefix_ptr)))
1160   {
1161     *ret_ptr++ = *prefix_ptr++;
1162     ident++;
1163     i++;
1164   }
1165   if (i == ident_len)
1166   {
1167     /* match, complete missing bits */
1168     while (i < 4)
1169     {
1170       *ret_ptr++ = *prefix_ptr++;
1171       i++;
1172     }
1173     oidret->len = i;
1174     return 1;
1175   }
1176   else
1177   {
1178     /* i != ident_len */
1179     return 0;
1180   }
1181 }
1182
1183 #endif /* LWIP_SNMP */