epan/frame_data_sequence.c

   1 /* frame_data_sequence.c
   2  * Implements a sequence of frame_data structures
   3  *
   4  * Wireshark - Network traffic analyzer
   5  * By Gerald Combs <gerald@wireshark.org>
   6  * Copyright 1998 Gerald Combs
   7  *
   8  * SPDX-License-Identifier: GPL-2.0-or-later
   9  */
  10
  11 #include "config.h"
  12
  13 #include <glib.h>
  14
  15 #include <epan/packet.h>
  16
  17 #include "frame_data_sequence.h"
  18
  19 /*
  20  * We store the frame_data structures in a radix tree, with 1024
  21  * elements per level.  The leaf nodes are arrays of 1024 frame_data
  22  * structures; the nodes above them are arrays of 1024 pointers to
  23  * the nodes below them.  The capture_file structure has a pointer
  24  * to the root node.
  25  *
  26  * As frame numbers are 32 bits, and as 1024 is 2^10, that gives us
  27  * up to 4 levels of tree.
  28  */
  29 #define LOG2_NODES_PER_LEVEL    10
  30 #define NODES_PER_LEVEL         (1<<LOG2_NODES_PER_LEVEL)
  31
  32 struct _frame_data_sequence {
  33   uint32_t     count;           /* Total number of frames */
  34   void        *ptree_root;      /* Pointer to the root node */
  35 };
  36
  37 /*
  38  * For a given frame number, calculate the indices into a level 3
  39  * node, a level 2 node, a level 1 node, and a leaf node.
  40  */
  41 #define LEVEL_3_INDEX(framenum) \
  42         ((framenum) >> (3*LOG2_NODES_PER_LEVEL))
  43 #define LEVEL_2_INDEX(framenum) \
  44         (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
  45 #define LEVEL_1_INDEX(framenum) \
  46         (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
  47 #define LEAF_INDEX(framenum) \
  48         (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
  49
  50 frame_data_sequence *
  51 new_frame_data_sequence(void)
  52 {
  53   frame_data_sequence *fds;
  54
  55   fds = (frame_data_sequence *)g_malloc(sizeof *fds);
  56   fds->count = 0;
  57   fds->ptree_root = NULL;
  58   return fds;
  59 }
  60
  61 /*
  62  * Add a new frame_data structure to a frame_data_sequence.
  63  */
  64 frame_data *
  65 frame_data_sequence_add(frame_data_sequence *fds, frame_data *fdata)
  66 {
  67   frame_data *leaf;
  68   frame_data **level1;
  69   frame_data ***level2;
  70   frame_data ****level3;
  71   frame_data *node;
  72
  73   /*
  74    * The current value of fds->count is the index value for the new frame,
  75    * because the index value for a frame is the frame number - 1, and
  76    * if we currently have fds->count frames, the the frame number of
  77    * the last frame in the collection is fds->count, so its index value
  78    * is fds->count - 1.
  79    */
  80   if (fds->count == 0) {
  81     /* The tree is empty; allocate the first leaf node, which will be
  82        the root node. */
  83     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
  84     node = &leaf[0];
  85     fds->ptree_root = leaf;
  86   } else if (fds->count < NODES_PER_LEVEL) {
  87     /* It's a 1-level tree, and is going to stay that way for now. */
  88     leaf = (frame_data *)fds->ptree_root;
  89     node = &leaf[fds->count];
  90   } else if (fds->count == NODES_PER_LEVEL) {
  91     /* It's a 1-level tree that will turn into a 2-level tree. */
  92     level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
  93     level1[0] = (frame_data *)fds->ptree_root;
  94     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
  95     level1[1] = leaf;
  96     node = &leaf[0];
  97     fds->ptree_root = level1;
  98   } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL) {
  99     /* It's a 2-level tree, and is going to stay that way for now. */
 100     level1 = (frame_data **)fds->ptree_root;
 101     leaf = level1[fds->count >> LOG2_NODES_PER_LEVEL];
 102     if (leaf == NULL) {
 103       leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 104       level1[fds->count >> LOG2_NODES_PER_LEVEL] = leaf;
 105     }
 106     node = &leaf[LEAF_INDEX(fds->count)];
 107   } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL) {
 108     /* It's a 2-level tree that will turn into a 3-level tree */
 109     level2 = (frame_data ***)g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 110     level2[0] = (frame_data **)fds->ptree_root;
 111     level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 112     level2[1] = level1;
 113     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 114     level1[0] = leaf;
 115     node = &leaf[0];
 116     fds->ptree_root = level2;
 117   } else if (fds->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 118     /* It's a 3-level tree, and is going to stay that way for now. */
 119     level2 = (frame_data ***)fds->ptree_root;
 120     level1 = level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 121     if (level1 == NULL) {
 122       level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 123       level2[fds->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1;
 124     }
 125     leaf = level1[LEVEL_1_INDEX(fds->count)];
 126     if (leaf == NULL) {
 127       leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 128       level1[LEVEL_1_INDEX(fds->count)] = leaf;
 129     }
 130     node = &leaf[LEAF_INDEX(fds->count)];
 131   } else if (fds->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 132     /* It's a 3-level tree that will turn into a 4-level tree */
 133     level3 = (frame_data ****)g_malloc0((sizeof *level3)*NODES_PER_LEVEL);
 134     level3[0] = (frame_data ***)fds->ptree_root;
 135     level2 = (frame_data ***)g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 136     level3[1] = level2;
 137     level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 138     level2[0] = level1;
 139     leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 140     level1[0] = leaf;
 141     node = &leaf[0];
 142     fds->ptree_root = level3;
 143   } else {
 144     /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 145        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 146        so fds->count is always less < NODES_PER_LEVEL^4.
 147
 148        XXX - we should fail if fds->count is 2^31-1, or should
 149        make the frame numbers 64-bit and just let users run
 150        themselves out of address space or swap space. :-) */
 151     /* It's a 4-level tree, and is going to stay that way forever. */
 152     level3 = (frame_data ****)fds->ptree_root;
 153     level2 = level3[LEVEL_3_INDEX(fds->count)];
 154     if (level2 == NULL) {
 155       level2 = (frame_data ***)g_malloc0((sizeof *level2)*NODES_PER_LEVEL);
 156       level3[LEVEL_3_INDEX(fds->count)] = level2;
 157     }
 158     level1 = level2[LEVEL_2_INDEX(fds->count)];
 159     if (level1 == NULL) {
 160       level1 = (frame_data **)g_malloc0((sizeof *level1)*NODES_PER_LEVEL);
 161       level2[LEVEL_2_INDEX(fds->count)] = level1;
 162     }
 163     leaf = level1[LEVEL_1_INDEX(fds->count)];
 164     if (leaf == NULL) {
 165       leaf = (frame_data *)g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
 166       level1[LEVEL_1_INDEX(fds->count)] = leaf;
 167     }
 168     node = &leaf[LEAF_INDEX(fds->count)];
 169   }
 170   *node = *fdata;
 171   fds->count++;
 172   return node;
 173 }
 174
 175 /*
 176  * Find the frame_data for the specified frame number.
 177  */
 178 frame_data *
 179 frame_data_sequence_find(frame_data_sequence *fds, uint32_t num)
 180 {
 181   frame_data *leaf;
 182   frame_data **level1;
 183   frame_data ***level2;
 184   frame_data ****level3;
 185
 186   if (num == 0 || fds == NULL) {
 187     /* There is no frame number 0 */
 188     return NULL;
 189   }
 190
 191   /* Convert it into an index number. */
 192   num--;
 193   if (num >= fds->count) {
 194     /* There aren't that many frames. */
 195     return NULL;
 196   }
 197
 198   if (fds->count <= NODES_PER_LEVEL) {
 199     /* It's a 1-level tree. */
 200     leaf = (frame_data *)fds->ptree_root;
 201     return &leaf[num];
 202   }
 203   if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
 204     /* It's a 2-level tree. */
 205     level1 = (frame_data **)fds->ptree_root;
 206     leaf = level1[num >> LOG2_NODES_PER_LEVEL];
 207     return &leaf[LEAF_INDEX(num)];
 208   }
 209   if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 210     /* It's a 3-level tree. */
 211     level2 = (frame_data ***)fds->ptree_root;
 212     level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 213     leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
 214     return &leaf[LEAF_INDEX(num)];
 215   }
 216   /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 217      2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 218      so fds->count is always less < NODES_PER_LEVEL^4. */
 219   /* It's a 4-level tree, and is going to stay that way forever. */
 220   level3 = (frame_data ****)fds->ptree_root;
 221   level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
 222   level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)];
 223   leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
 224   return &leaf[LEAF_INDEX(num)];
 225 }
 226
 227 /* recursively frees a frame_data radix level */
 228 static void
 229 // NOLINTNEXTLINE(misc-no-recursion)
 230 free_frame_data_array(void *array, unsigned count, unsigned level, bool last)
 231 {
 232   unsigned i, level_count;
 233
 234   if (last) {
 235     /* if we are the last in our given parent's row, we may not have
 236      * exactly a full row, so do the bit twiddling to figure out exactly
 237      * how many fields we have */
 238     level_count = (count >> ((level - 1) * LOG2_NODES_PER_LEVEL)) &
 239                   (NODES_PER_LEVEL - 1);
 240     /* the above calculation rounds down, so make sure we count correctly
 241      * if count is not an even multiple of NODES_PER_LEVEL */
 242     if (count & ((1 << ((level - 1) * LOG2_NODES_PER_LEVEL)) - 1)) {
 243       level_count++;
 244     }
 245   }
 246   else {
 247     /* if we're not the last in our parent, then we're guaranteed to have
 248      * a full array */
 249     level_count = NODES_PER_LEVEL;
 250   }
 251
 252
 253   if (level > 1) {
 254     /* recurse on every sub-array, passing on our own 'last' value
 255      * specially to our last child */
 256     frame_data **real_array = (frame_data **) array;
 257
 258     for (i=0; i < level_count-1; i++) {
 259       // We recurse here, but we're limited to four levels.
 260       free_frame_data_array(real_array[i], count, level-1, false);
 261     }
 262
 263     // We recurse here, but we're limited to four levels.
 264     free_frame_data_array(real_array[level_count-1], count, level-1, last);
 265   }
 266   else if (level == 1) {
 267     /* bottom level, so just clean up all the frame data */
 268     frame_data *real_array = (frame_data *) array;
 269
 270     for (i=0; i < level_count; i++) {
 271       frame_data_destroy(&real_array[i]);
 272     }
 273   }
 274
 275   /* free the array itself */
 276   g_free(array);
 277 }
 278
 279 /*
 280  * Free a frame_data_sequence and all the frame_data structures in it.
 281  */
 282 void
 283 free_frame_data_sequence(frame_data_sequence *fds)
 284 {
 285   unsigned   levels;
 286
 287   /* calculate how many levels we have */
 288   if (fds->count == 0) {
 289     /* The tree is empty; there are no levels. */
 290     levels = 0;
 291   } else if (fds->count <= NODES_PER_LEVEL) {
 292     /* It's a 1-level tree. */
 293     levels = 1;
 294   } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
 295     /* It's a 2-level tree. */
 296     levels = 2;
 297   } else if (fds->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
 298     /* It's a 3-level tree. */
 299     levels = 3;
 300   } else {
 301     /* fds->count is 2^32-1 at most, and NODES_PER_LEVEL^4
 302        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
 303        so fds->count is always less < NODES_PER_LEVEL^4. */
 304     /* It's a 4-level tree. */
 305     levels = 4;
 306   }
 307
 308   /* call the recursive free function */
 309   if (levels > 0) {
 310     free_frame_data_array(fds->ptree_root, fds->count, levels, true);
 311   }
 312
 313   /* free the header struct */
 314   g_free(fds);
 315 }
 316
 317 void
 318 find_and_mark_frame_depended_upon(void *key, void *value _U_, void *user_data)
 319 {
 320   frame_data   *dependent_fd;
 321   uint32_t      dependent_frame = GPOINTER_TO_UINT(key);
 322   frame_data_sequence *frames   = (frame_data_sequence *)user_data;
 323
 324   if (dependent_frame && frames) {
 325     dependent_fd = frame_data_sequence_find(frames, dependent_frame);
 326     /* Don't recurse for packets we've already marked. Note we assume that no
 327      * packet depends on a future packet; we assume that in other places too.
 328      */
 329     if (!(dependent_fd->dependent_of_displayed || dependent_fd->passed_dfilter)) {
 330       dependent_fd->dependent_of_displayed = 1;
 331       if (dependent_fd->dependent_frames) {
 332         g_hash_table_foreach(dependent_fd->dependent_frames, find_and_mark_frame_depended_upon, frames);
 333       }
 334     }
 335   }
 336 }
 337
 338 /*
 339  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 340  *
 341  * Local variables:
 342  * c-basic-offset: 2
 343  * tab-width: 8
 344  * indent-tabs-mode: nil
 345  * End:
 346  *
 347  * vi: set shiftwidth=2 tabstop=8 expandtab:
 348  * :indentSize=2:tabSize=8:noTabs=true:
 349  */