lwip/src/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 != 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 */