vnet/vnet/fib/fib_entry_cover.c

   1 /*
   2  * Copyright (c) 2016 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <vnet/fib/fib_entry_cover.h>
  17 #include <vnet/fib/fib_entry_src.h>
  18 #include <vnet/fib/fib_node_list.h>
  19
  20 u32
  21 fib_entry_cover_track (fib_entry_t* cover,
  22                        fib_node_index_t covered)
  23 {
  24     FIB_ENTRY_DBG(cover, "cover-track %d", covered);
  25
  26     ASSERT(fib_entry_get_index(cover) != covered);
  27
  28     if (FIB_NODE_INDEX_INVALID == cover->fe_covered)
  29     {
  30         cover->fe_covered = fib_node_list_create();
  31     }
  32
  33     return (fib_node_list_push_front(cover->fe_covered,
  34                                      0, FIB_NODE_TYPE_ENTRY,
  35                                      covered));
  36 }
  37
  38 void
  39 fib_entry_cover_untrack (fib_entry_t* cover,
  40                          u32 tracked_index)
  41 {
  42     FIB_ENTRY_DBG(cover, "cover-untrack @ %d", tracked_index);
  43
  44     if (FIB_NODE_INDEX_INVALID == cover->fe_covered)
  45         return;
  46
  47     fib_node_list_remove(cover->fe_covered, tracked_index);
  48
  49     if (0 == fib_node_list_get_size(cover->fe_covered))
  50     {
  51         fib_node_list_destroy(&cover->fe_covered);
  52     }
  53 }
  54
  55 /**
  56  * Internal struct to hold user supplied paraneters for the cover walk
  57  */
  58 typedef struct fib_enty_cover_walk_ctx_t_ {
  59     fib_entry_t *cover;
  60     fib_entry_covered_walk_t walk;
  61     void *ctx;
  62 } fib_enty_cover_walk_ctx_t;
  63
  64 static int
  65 fib_entry_cover_walk_node_ptr (fib_node_ptr_t *depend,
  66                                void *args)
  67 {
  68     fib_enty_cover_walk_ctx_t *ctx = args;
  69
  70     ctx->walk(ctx->cover, depend->fnp_index, ctx->ctx);
  71
  72     /* continue */
  73     return (1);
  74 }
  75
  76 void
  77 fib_entry_cover_walk (fib_entry_t *cover,
  78                       fib_entry_covered_walk_t walk,
  79                       void *args)
  80 {
  81     if (FIB_NODE_INDEX_INVALID != cover->fe_covered)
  82     {
  83         fib_enty_cover_walk_ctx_t ctx = {
  84             .cover = cover,
  85             .walk = walk,
  86             .ctx = args,
  87         };
  88
  89         fib_node_list_walk(cover->fe_covered,
  90                            fib_entry_cover_walk_node_ptr,
  91                            &ctx);
  92     }
  93 }
  94
  95 u32
  96 fib_entry_cover_get_size (fib_entry_t *cover)
  97 {
  98     if (FIB_NODE_INDEX_INVALID != cover->fe_covered)
  99         return (fib_node_list_get_size(cover->fe_covered));
 100     return (0);
 101 }
 102
 103 typedef struct fib_entry_cover_list_format_ctx_t_ {
 104     u8 *s;
 105 } fib_entry_cover_list_format_ctx_t;
 106
 107 static int
 108 fib_entry_covered_list_format_one (fib_entry_t *cover,
 109                                    fib_node_index_t covered,
 110                                    void *args)
 111 {
 112     fib_entry_cover_list_format_ctx_t * ctx = args;
 113
 114     ctx->s = format(ctx->s, "%d, ", covered);
 115
 116     /* continue */
 117     return (1);
 118 }
 119
 120 u8*
 121 fib_entry_cover_list_format (fib_entry_t *fib_entry,
 122                              u8 *s)
 123 {
 124     fib_entry_cover_list_format_ctx_t ctx = {
 125         .s = s,
 126     };
 127
 128     fib_entry_cover_walk(fib_entry,
 129                          fib_entry_covered_list_format_one,
 130                          &ctx);
 131
 132     return (ctx.s);
 133 }
 134
 135 static int
 136 fib_entry_cover_change_one (fib_entry_t *cover,
 137                             fib_node_index_t covered,
 138                             void *args)
 139 {
 140     fib_node_index_t new_cover;
 141
 142     /*
 143      * The 3 entries involved here are:
 144      *   cover - the least specific. It will cover both the others
 145      *  new_cover - the enty just inserted below the cover
 146      *  covered - the entry that was tracking the cover.
 147      *
 148      * The checks below are to determine if new_cover is a cover for covered.
 149      */
 150     new_cover = pointer_to_uword(args);
 151
 152     if (FIB_NODE_INDEX_INVALID == new_cover)
 153     {
 154         /*
 155          * nothing has been inserted, which implies the cover was removed.
 156          * 'cover' is thus the new cover.
 157          */
 158         fib_entry_cover_changed(covered);
 159     }
 160     else if (new_cover != covered)
 161     {
 162         fib_prefix_t pfx_covered, pfx_new_cover;
 163
 164         fib_entry_get_prefix(covered, &pfx_covered);
 165         fib_entry_get_prefix(new_cover, &pfx_new_cover);
 166
 167         if (fib_prefix_is_cover(&pfx_new_cover, &pfx_covered))
 168         {
 169             fib_entry_cover_changed(covered);
 170         }
 171     }
 172     /* continue */
 173     return (1);
 174 }
 175
 176 void
 177 fib_entry_cover_change_notify (fib_node_index_t cover_index,
 178                                fib_node_index_t covered)
 179 {
 180     fib_entry_t *cover;
 181
 182     cover = fib_entry_get(cover_index);
 183
 184     fib_entry_cover_walk(cover,
 185                          fib_entry_cover_change_one,
 186                          uword_to_pointer(covered, void*));
 187 }
 188
 189 static int
 190 fib_entry_cover_update_one (fib_entry_t *cover,
 191                             fib_node_index_t covered,
 192                             void *args)
 193 {
 194     fib_entry_cover_updated(covered);
 195
 196     /* continue */
 197     return (1);
 198 }
 199
 200 void
 201 fib_entry_cover_update_notify (fib_entry_t *fib_entry)
 202 {
 203     fib_entry_cover_walk(fib_entry,
 204                          fib_entry_cover_update_one,
 205                          NULL);
 206 }