lib/prefix.c

   1 /*
   2  * Prefix related functions.
   3  * Copyright (C) 1997, 98, 99 Kunihiro Ishiguro
   4  *
   5  * This file is part of GNU Zebra.
   6  *
   7  * GNU Zebra is free software; you can redistribute it and/or modify it
   8  * under the terms of the GNU General Public License as published by the
   9  * Free Software Foundation; either version 2, or (at your option) any
  10  * later version.
  11  *
  12  * GNU Zebra is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License along
  18  * with this program; see the file COPYING; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 #include <zebra.h>
  23
  24 #include "prefix.h"
  25 #include "vty.h"
  26 #include "sockunion.h"
  27 #include "memory.h"
  28 #include "log.h"
  29 #include "jhash.h"
  30
  31 DEFINE_MTYPE_STATIC(LIB, PREFIX, "Prefix")
  32
  33 /* Maskbit. */
  34 static const u_char maskbit[] = {0x00, 0x80, 0xc0, 0xe0, 0xf0,
  35                                  0xf8, 0xfc, 0xfe, 0xff};
  36
  37 static const struct in6_addr maskbytes6[] = {
  38         /* /0   */ {{{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  39                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  40         /* /1   */ {{{0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  41                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  42         /* /2   */ {{{0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  43                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  44         /* /3   */ {{{0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  45                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  46         /* /4   */ {{{0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  47                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  48         /* /5   */ {{{0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  49                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  50         /* /6   */ {{{0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  51                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  52         /* /7   */ {{{0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  53                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  54         /* /8   */ {{{0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  55                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  56         /* /9   */ {{{0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  57                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  58         /* /10  */ {{{0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  59                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  60         /* /11  */ {{{0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  61                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  62         /* /12  */ {{{0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  63                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  64         /* /13  */ {{{0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  65                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  66         /* /14  */ {{{0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  67                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  68         /* /15  */ {{{0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  69                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  70         /* /16  */ {{{0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  71                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  72         /* /17  */ {{{0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  73                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  74         /* /18  */ {{{0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  75                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  76         /* /19  */ {{{0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  77                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  78         /* /20  */ {{{0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  79                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  80         /* /21  */ {{{0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  81                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  82         /* /22  */ {{{0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  83                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  84         /* /23  */ {{{0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  85                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  86         /* /24  */ {{{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  87                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  88         /* /25  */ {{{0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00,
  89                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  90         /* /26  */ {{{0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00,
  91                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  92         /* /27  */ {{{0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00,
  93                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  94         /* /28  */ {{{0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00,
  95                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  96         /* /29  */ {{{0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00,
  97                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
  98         /* /30  */ {{{0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00,
  99                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 100         /* /31  */ {{{0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00,
 101                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 102         /* /32  */ {{{0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
 103                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 104         /* /33  */ {{{0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00,
 105                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 106         /* /34  */ {{{0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00,
 107                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 108         /* /35  */ {{{0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00,
 109                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 110         /* /36  */ {{{0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00,
 111                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 112         /* /37  */ {{{0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00,
 113                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 114         /* /38  */ {{{0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00,
 115                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 116         /* /39  */ {{{0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00,
 117                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 118         /* /40  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
 119                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 120         /* /41  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00,
 121                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 122         /* /42  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00,
 123                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 124         /* /43  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00,
 125                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 126         /* /44  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00,
 127                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 128         /* /45  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00,
 129                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 130         /* /46  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00,
 131                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 132         /* /47  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00,
 133                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 134         /* /48  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00,
 135                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 136         /* /49  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00,
 137                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 138         /* /50  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00,
 139                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 140         /* /51  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00,
 141                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 142         /* /52  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00,
 143                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 144         /* /53  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00,
 145                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 146         /* /54  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00,
 147                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 148         /* /55  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00,
 149                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 150         /* /56  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00,
 151                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 152         /* /57  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00,
 153                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 154         /* /58  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00,
 155                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 156         /* /59  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00,
 157                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 158         /* /60  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00,
 159                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 160         /* /61  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00,
 161                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 162         /* /62  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00,
 163                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 164         /* /63  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00,
 165                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 166         /* /64  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
 167                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 168         /* /65  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80,
 169                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 170         /* /66  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0,
 171                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 172         /* /67  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0,
 173                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 174         /* /68  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0,
 175                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 176         /* /69  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8,
 177                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 178         /* /70  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc,
 179                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 180         /* /71  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
 181                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 182         /* /72  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 183                       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 184         /* /73  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 185                       0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 186         /* /74  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 187                       0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 188         /* /75  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 189                       0xe0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 190         /* /76  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 191                       0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 192         /* /77  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 193                       0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 194         /* /78  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 195                       0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 196         /* /79  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 197                       0xfe, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 198         /* /80  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 199                       0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 200         /* /81  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 201                       0xff, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 202         /* /82  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 203                       0xff, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 204         /* /83  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 205                       0xff, 0xe0, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 206         /* /84  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 207                       0xff, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 208         /* /85  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 209                       0xff, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 210         /* /86  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 211                       0xff, 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 212         /* /87  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 213                       0xff, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 214         /* /88  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 215                       0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00}}},
 216         /* /89  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 217                       0xff, 0xff, 0x80, 0x00, 0x00, 0x00, 0x00}}},
 218         /* /90  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 219                       0xff, 0xff, 0xc0, 0x00, 0x00, 0x00, 0x00}}},
 220         /* /91  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 221                       0xff, 0xff, 0xe0, 0x00, 0x00, 0x00, 0x00}}},
 222         /* /92  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 223                       0xff, 0xff, 0xf0, 0x00, 0x00, 0x00, 0x00}}},
 224         /* /93  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 225                       0xff, 0xff, 0xf8, 0x00, 0x00, 0x00, 0x00}}},
 226         /* /94  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 227                       0xff, 0xff, 0xfc, 0x00, 0x00, 0x00, 0x00}}},
 228         /* /95  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 229                       0xff, 0xff, 0xfe, 0x00, 0x00, 0x00, 0x00}}},
 230         /* /96  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 231                       0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00}}},
 232         /* /97  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 233                       0xff, 0xff, 0xff, 0x80, 0x00, 0x00, 0x00}}},
 234         /* /98  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 235                       0xff, 0xff, 0xff, 0xc0, 0x00, 0x00, 0x00}}},
 236         /* /99  */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 237                       0xff, 0xff, 0xff, 0xe0, 0x00, 0x00, 0x00}}},
 238         /* /100 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 239                       0xff, 0xff, 0xff, 0xf0, 0x00, 0x00, 0x00}}},
 240         /* /101 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 241                       0xff, 0xff, 0xff, 0xf8, 0x00, 0x00, 0x00}}},
 242         /* /102 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 243                       0xff, 0xff, 0xff, 0xfc, 0x00, 0x00, 0x00}}},
 244         /* /103 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 245                       0xff, 0xff, 0xff, 0xfe, 0x00, 0x00, 0x00}}},
 246         /* /104 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 247                       0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00}}},
 248         /* /105 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 249                       0xff, 0xff, 0xff, 0xff, 0x80, 0x00, 0x00}}},
 250         /* /106 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 251                       0xff, 0xff, 0xff, 0xff, 0xc0, 0x00, 0x00}}},
 252         /* /107 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 253                       0xff, 0xff, 0xff, 0xff, 0xe0, 0x00, 0x00}}},
 254         /* /108 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 255                       0xff, 0xff, 0xff, 0xff, 0xf0, 0x00, 0x00}}},
 256         /* /109 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 257                       0xff, 0xff, 0xff, 0xff, 0xf8, 0x00, 0x00}}},
 258         /* /110 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 259                       0xff, 0xff, 0xff, 0xff, 0xfc, 0x00, 0x00}}},
 260         /* /111 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 261                       0xff, 0xff, 0xff, 0xff, 0xfe, 0x00, 0x00}}},
 262         /* /112 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 263                       0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00}}},
 264         /* /113 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 265                       0xff, 0xff, 0xff, 0xff, 0xff, 0x80, 0x00}}},
 266         /* /114 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 267                       0xff, 0xff, 0xff, 0xff, 0xff, 0xc0, 0x00}}},
 268         /* /115 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 269                       0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0x00}}},
 270         /* /116 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 271                       0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x00}}},
 272         /* /117 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 273                       0xff, 0xff, 0xff, 0xff, 0xff, 0xf8, 0x00}}},
 274         /* /118 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 275                       0xff, 0xff, 0xff, 0xff, 0xff, 0xfc, 0x00}}},
 276         /* /119 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 277                       0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0x00}}},
 278         /* /120 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 279                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00}}},
 280         /* /121 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 281                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80}}},
 282         /* /122 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 283                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xc0}}},
 284         /* /123 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 285                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe0}}},
 286         /* /124 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 287                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0}}},
 288         /* /125 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 289                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf8}}},
 290         /* /126 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 291                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfc}}},
 292         /* /127 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 293                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe}}},
 294         /* /128 */ {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 295                       0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}}}};
 296
 297 /* Number of bits in prefix type. */
 298 #ifndef PNBBY
 299 #define PNBBY 8
 300 #endif /* PNBBY */
 301
 302 #define MASKBIT(offset)  ((0xff << (PNBBY - (offset))) & 0xff)
 303
 304 static int is_zero_mac(const struct ethaddr *mac)
 305 {
 306         int i = 0;
 307
 308         for (i = 0; i < ETH_ALEN; i++) {
 309                 if (mac->octet[i])
 310                         return 0;
 311         }
 312
 313         return 1;
 314 }
 315
 316 unsigned int prefix_bit(const u_char *prefix, const u_char prefixlen)
 317 {
 318         unsigned int offset = prefixlen / 8;
 319         unsigned int shift = 7 - (prefixlen % 8);
 320
 321         return (prefix[offset] >> shift) & 1;
 322 }
 323
 324 unsigned int prefix6_bit(const struct in6_addr *prefix, const u_char prefixlen)
 325 {
 326         return prefix_bit((const u_char *)&prefix->s6_addr, prefixlen);
 327 }
 328
 329 int str2family(const char *string)
 330 {
 331         if (!strcmp("ipv4", string))
 332                 return AF_INET;
 333         else if (!strcmp("ipv6", string))
 334                 return AF_INET6;
 335         else if (!strcmp("ethernet", string))
 336                 return AF_ETHERNET;
 337         else if (!strcmp("evpn", string))
 338                 return AF_EVPN;
 339         return -1;
 340 }
 341
 342 /* Address Famiy Identifier to Address Family converter. */
 343 int afi2family(afi_t afi)
 344 {
 345         if (afi == AFI_IP)
 346                 return AF_INET;
 347         else if (afi == AFI_IP6)
 348                 return AF_INET6;
 349         else if (afi == AFI_L2VPN)
 350                 return AF_ETHERNET;
 351         /* NOTE: EVPN code should NOT use this interface. */
 352         return 0;
 353 }
 354
 355 afi_t family2afi(int family)
 356 {
 357         if (family == AF_INET)
 358                 return AFI_IP;
 359         else if (family == AF_INET6)
 360                 return AFI_IP6;
 361         else if (family == AF_ETHERNET || family == AF_EVPN)
 362                 return AFI_L2VPN;
 363         return 0;
 364 }
 365
 366 const char *afi2str(afi_t afi)
 367 {
 368         switch (afi) {
 369         case AFI_IP:
 370                 return "IPv4";
 371         case AFI_IP6:
 372                 return "IPv6";
 373         case AFI_L2VPN:
 374                 return "l2vpn";
 375         case AFI_MAX:
 376                 return "bad-value";
 377         default:
 378                 break;
 379         }
 380         return NULL;
 381 }
 382
 383 const char *safi2str(safi_t safi)
 384 {
 385         switch (safi) {
 386         case SAFI_UNICAST:
 387                 return "unicast";
 388         case SAFI_MULTICAST:
 389                 return "multicast";
 390         case SAFI_MPLS_VPN:
 391                 return "vpn";
 392         case SAFI_ENCAP:
 393                 return "encap";
 394         case SAFI_EVPN:
 395                 return "evpn";
 396         case SAFI_LABELED_UNICAST:
 397                 return "labeled-unicast";
 398         default:
 399                 return "unknown";
 400         }
 401 }
 402
 403 /* If n includes p prefix then return 1 else return 0. */
 404 int prefix_match(const struct prefix *n, const struct prefix *p)
 405 {
 406         int offset;
 407         int shift;
 408         const u_char *np, *pp;
 409
 410         /* If n's prefix is longer than p's one return 0. */
 411         if (n->prefixlen > p->prefixlen)
 412                 return 0;
 413
 414         /* Set both prefix's head pointer. */
 415         np = (const u_char *)&n->u.prefix;
 416         pp = (const u_char *)&p->u.prefix;
 417
 418         offset = n->prefixlen / PNBBY;
 419         shift = n->prefixlen % PNBBY;
 420
 421         if (shift)
 422                 if (maskbit[shift] & (np[offset] ^ pp[offset]))
 423                         return 0;
 424
 425         while (offset--)
 426                 if (np[offset] != pp[offset])
 427                         return 0;
 428         return 1;
 429 }
 430
 431 /* If n includes p then return 1 else return 0. Prefix mask is not considered */
 432 int prefix_match_network_statement(const struct prefix *n,
 433                                    const struct prefix *p)
 434 {
 435         int offset;
 436         int shift;
 437         const u_char *np, *pp;
 438
 439         /* Set both prefix's head pointer. */
 440         np = (const u_char *)&n->u.prefix;
 441         pp = (const u_char *)&p->u.prefix;
 442
 443         offset = n->prefixlen / PNBBY;
 444         shift = n->prefixlen % PNBBY;
 445
 446         if (shift)
 447                 if (maskbit[shift] & (np[offset] ^ pp[offset]))
 448                         return 0;
 449
 450         while (offset--)
 451                 if (np[offset] != pp[offset])
 452                         return 0;
 453         return 1;
 454 }
 455
 456 /* Copy prefix from src to dest. */
 457 void prefix_copy(struct prefix *dest, const struct prefix *src)
 458 {
 459         dest->family = src->family;
 460         dest->prefixlen = src->prefixlen;
 461
 462         if (src->family == AF_INET)
 463                 dest->u.prefix4 = src->u.prefix4;
 464         else if (src->family == AF_INET6)
 465                 dest->u.prefix6 = src->u.prefix6;
 466         else if (src->family == AF_ETHERNET) {
 467                 memcpy(&dest->u.prefix_eth, &src->u.prefix_eth,
 468                        sizeof(struct ethaddr));
 469         } else if (src->family == AF_EVPN) {
 470                 memcpy(&dest->u.prefix_evpn, &src->u.prefix_evpn,
 471                        sizeof(struct evpn_addr));
 472         } else if (src->family == AF_UNSPEC) {
 473                 dest->u.lp.id = src->u.lp.id;
 474                 dest->u.lp.adv_router = src->u.lp.adv_router;
 475         } else {
 476                 zlog_err("prefix_copy(): Unknown address family %d",
 477                          src->family);
 478                 assert(0);
 479         }
 480 }
 481
 482 /*
 483  * Return 1 if the address/netmask contained in the prefix structure
 484  * is the same, and else return 0.  For this routine, 'same' requires
 485  * that not only the prefix length and the network part be the same,
 486  * but also the host part.  Thus, 10.0.0.1/8 and 10.0.0.2/8 are not
 487  * the same.  Note that this routine has the same return value sense
 488  * as '==' (which is different from prefix_cmp).
 489  */
 490 int prefix_same(const struct prefix *p1, const struct prefix *p2)
 491 {
 492         if ((p1 && !p2) || (!p1 && p2))
 493                 return 0;
 494
 495         if (!p1 && !p2)
 496                 return 1;
 497
 498         if (p1->family == p2->family && p1->prefixlen == p2->prefixlen) {
 499                 if (p1->family == AF_INET)
 500                         if (IPV4_ADDR_SAME(&p1->u.prefix4, &p2->u.prefix4))
 501                                 return 1;
 502                 if (p1->family == AF_INET6)
 503                         if (IPV6_ADDR_SAME(&p1->u.prefix6.s6_addr,
 504                                            &p2->u.prefix6.s6_addr))
 505                                 return 1;
 506                 if (p1->family == AF_ETHERNET)
 507                         if (!memcmp(&p1->u.prefix_eth, &p2->u.prefix_eth,
 508                                     sizeof(struct ethaddr)))
 509                                 return 1;
 510                 if (p1->family == AF_EVPN)
 511                         if (!memcmp(&p1->u.prefix_evpn, &p2->u.prefix_evpn,
 512                                     sizeof(struct evpn_addr)))
 513                                 return 1;
 514         }
 515         return 0;
 516 }
 517
 518 /*
 519  * Return 0 if the network prefixes represented by the struct prefix
 520  * arguments are the same prefix, and 1 otherwise.  Network prefixes
 521  * are considered the same if the prefix lengths are equal and the
 522  * network parts are the same.  Host bits (which are considered masked
 523  * by the prefix length) are not significant.  Thus, 10.0.0.1/8 and
 524  * 10.0.0.2/8 are considered equivalent by this routine.  Note that
 525  * this routine has the same return sense as strcmp (which is different
 526  * from prefix_same).
 527  */
 528 int prefix_cmp(const struct prefix *p1, const struct prefix *p2)
 529 {
 530         int offset;
 531         int shift;
 532
 533         /* Set both prefix's head pointer. */
 534         const u_char *pp1 = (const u_char *)&p1->u.prefix;
 535         const u_char *pp2 = (const u_char *)&p2->u.prefix;
 536
 537         if (p1->family != p2->family || p1->prefixlen != p2->prefixlen)
 538                 return 1;
 539
 540         offset = p1->prefixlen / PNBBY;
 541         shift = p1->prefixlen % PNBBY;
 542
 543         if (shift)
 544                 if (maskbit[shift] & (pp1[offset] ^ pp2[offset]))
 545                         return 1;
 546
 547         while (offset--)
 548                 if (pp1[offset] != pp2[offset])
 549                         return 1;
 550
 551         return 0;
 552 }
 553
 554 /*
 555  * Count the number of common bits in 2 prefixes. The prefix length is
 556  * ignored for this function; the whole prefix is compared. If the prefix
 557  * address families don't match, return -1; otherwise the return value is
 558  * in range 0 ... maximum prefix length for the address family.
 559  */
 560 int prefix_common_bits(const struct prefix *p1, const struct prefix *p2)
 561 {
 562         int pos, bit;
 563         int length = 0;
 564         u_char xor ;
 565
 566         /* Set both prefix's head pointer. */
 567         const u_char *pp1 = (const u_char *)&p1->u.prefix;
 568         const u_char *pp2 = (const u_char *)&p2->u.prefix;
 569
 570         if (p1->family == AF_INET)
 571                 length = IPV4_MAX_BYTELEN;
 572         if (p1->family == AF_INET6)
 573                 length = IPV6_MAX_BYTELEN;
 574         if (p1->family == AF_ETHERNET)
 575                 length = ETH_ALEN;
 576         if (p1->family == AF_EVPN)
 577                 length = 8 * sizeof(struct evpn_addr);
 578
 579         if (p1->family != p2->family || !length)
 580                 return -1;
 581
 582         for (pos = 0; pos < length; pos++)
 583                 if (pp1[pos] != pp2[pos])
 584                         break;
 585         if (pos == length)
 586                 return pos * 8;
 587
 588         xor = pp1[pos] ^ pp2[pos];
 589         for (bit = 0; bit < 8; bit++)
 590                 if (xor&(1 << (7 - bit)))
 591                         break;
 592
 593         return pos * 8 + bit;
 594 }
 595
 596 /* Return prefix family type string. */
 597 const char *prefix_family_str(const struct prefix *p)
 598 {
 599         if (p->family == AF_INET)
 600                 return "inet";
 601         if (p->family == AF_INET6)
 602                 return "inet6";
 603         if (p->family == AF_ETHERNET)
 604                 return "ether";
 605         if (p->family == AF_EVPN)
 606                 return "evpn";
 607         return "unspec";
 608 }
 609
 610 /* Allocate new prefix_ipv4 structure. */
 611 struct prefix_ipv4 *prefix_ipv4_new()
 612 {
 613         struct prefix_ipv4 *p;
 614
 615         /* Call prefix_new to allocate a full-size struct prefix to avoid
 616            problems
 617            where the struct prefix_ipv4 is cast to struct prefix and unallocated
 618            bytes were being referenced (e.g. in structure assignments). */
 619         p = (struct prefix_ipv4 *)prefix_new();
 620         p->family = AF_INET;
 621         return p;
 622 }
 623
 624 /* Free prefix_ipv4 structure. */
 625 void prefix_ipv4_free(struct prefix_ipv4 *p)
 626 {
 627         prefix_free((struct prefix *)p);
 628 }
 629
 630 /* When string format is invalid return 0. */
 631 int str2prefix_ipv4(const char *str, struct prefix_ipv4 *p)
 632 {
 633         int ret;
 634         int plen;
 635         char *pnt;
 636         char *cp;
 637
 638         /* Find slash inside string. */
 639         pnt = strchr(str, '/');
 640
 641         /* String doesn't contail slash. */
 642         if (pnt == NULL) {
 643                 /* Convert string to prefix. */
 644                 ret = inet_aton(str, &p->prefix);
 645                 if (ret == 0)
 646                         return 0;
 647
 648                 /* If address doesn't contain slash we assume it host address.
 649                  */
 650                 p->family = AF_INET;
 651                 p->prefixlen = IPV4_MAX_BITLEN;
 652
 653                 return ret;
 654         } else {
 655                 cp = XMALLOC(MTYPE_TMP, (pnt - str) + 1);
 656                 strncpy(cp, str, pnt - str);
 657                 *(cp + (pnt - str)) = '\0';
 658                 ret = inet_aton(cp, &p->prefix);
 659                 XFREE(MTYPE_TMP, cp);
 660
 661                 /* Get prefix length. */
 662                 plen = (u_char)atoi(++pnt);
 663                 if (plen > IPV4_MAX_PREFIXLEN)
 664                         return 0;
 665
 666                 p->family = AF_INET;
 667                 p->prefixlen = plen;
 668         }
 669
 670         return ret;
 671 }
 672
 673 /* When string format is invalid return 0. */
 674 int str2prefix_eth(const char *str, struct prefix_eth *p)
 675 {
 676         int ret = 0;
 677         int plen = 48;
 678         char *pnt;
 679         char *cp = NULL;
 680         const char *str_addr = str;
 681         unsigned int a[6];
 682         int i;
 683         bool slash = false;
 684
 685         if (!strcmp(str, "any")) {
 686                 memset(p, 0, sizeof(*p));
 687                 p->family = AF_ETHERNET;
 688                 return 1;
 689         }
 690
 691         /* Find slash inside string. */
 692         pnt = strchr(str, '/');
 693
 694         if (pnt) {
 695                 /* Get prefix length. */
 696                 plen = (u_char)atoi(++pnt);
 697                 if (plen > 48) {
 698                         ret = 0;
 699                         goto done;
 700                 }
 701
 702                 cp = XMALLOC(MTYPE_TMP, (pnt - str) + 1);
 703                 strncpy(cp, str, pnt - str);
 704                 *(cp + (pnt - str)) = '\0';
 705
 706                 str_addr = cp;
 707                 slash = true;
 708         }
 709
 710         /* Convert string to prefix. */
 711         if (sscanf(str_addr, "%2x:%2x:%2x:%2x:%2x:%2x", a + 0, a + 1, a + 2,
 712                    a + 3, a + 4, a + 5)
 713             != 6) {
 714                 ret = 0;
 715                 goto done;
 716         }
 717         for (i = 0; i < 6; ++i) {
 718                 p->eth_addr.octet[i] = a[i] & 0xff;
 719         }
 720         p->prefixlen = plen;
 721         p->family = AF_ETHERNET;
 722
 723         /*
 724          * special case to allow old configurations to work
 725          * Since all zero's is implicitly meant to allow
 726          * a comparison to zero, let's assume
 727          */
 728         if (!slash && is_zero_mac(&(p->eth_addr)))
 729             p->prefixlen = 0;
 730
 731         ret = 1;
 732
 733 done:
 734         if (cp)
 735                 XFREE(MTYPE_TMP, cp);
 736
 737         return ret;
 738 }
 739
 740 /* Convert masklen into IP address's netmask (network byte order). */
 741 void masklen2ip(const int masklen, struct in_addr *netmask)
 742 {
 743         assert(masklen >= 0 && masklen <= IPV4_MAX_BITLEN);
 744
 745         /* left shift is only defined for less than the size of the type.
 746          * we unconditionally use long long in case the target platform
 747          * has defined behaviour for << 32 (or has a 64-bit left shift) */
 748
 749         if (sizeof(unsigned long long) > 4)
 750                 netmask->s_addr = htonl(0xffffffffULL << (32 - masklen));
 751         else
 752                 netmask->s_addr =
 753                         htonl(masklen ? 0xffffffffU << (32 - masklen) : 0);
 754 }
 755
 756 /* Convert IP address's netmask into integer. We assume netmask is
 757    sequential one. Argument netmask should be network byte order. */
 758 u_char ip_masklen(struct in_addr netmask)
 759 {
 760         uint32_t tmp = ~ntohl(netmask.s_addr);
 761         if (tmp)
 762                 /* clz: count leading zeroes. sadly, the behaviour of this
 763                  * builtin
 764                  * is undefined for a 0 argument, even though most CPUs give 32
 765                  */
 766                 return __builtin_clz(tmp);
 767         else
 768                 return 32;
 769 }
 770
 771 /* Apply mask to IPv4 prefix (network byte order). */
 772 void apply_mask_ipv4(struct prefix_ipv4 *p)
 773 {
 774         struct in_addr mask;
 775         masklen2ip(p->prefixlen, &mask);
 776         p->prefix.s_addr &= mask.s_addr;
 777 }
 778
 779 /* If prefix is 0.0.0.0/0 then return 1 else return 0. */
 780 int prefix_ipv4_any(const struct prefix_ipv4 *p)
 781 {
 782         return (p->prefix.s_addr == 0 && p->prefixlen == 0);
 783 }
 784
 785 /* Allocate a new ip version 6 route */
 786 struct prefix_ipv6 *prefix_ipv6_new(void)
 787 {
 788         struct prefix_ipv6 *p;
 789
 790         /* Allocate a full-size struct prefix to avoid problems with structure
 791            size mismatches. */
 792         p = (struct prefix_ipv6 *)prefix_new();
 793         p->family = AF_INET6;
 794         return p;
 795 }
 796
 797 /* Free prefix for IPv6. */
 798 void prefix_ipv6_free(struct prefix_ipv6 *p)
 799 {
 800         prefix_free((struct prefix *)p);
 801 }
 802
 803 /* If given string is valid return pin6 else return NULL */
 804 int str2prefix_ipv6(const char *str, struct prefix_ipv6 *p)
 805 {
 806         char *pnt;
 807         char *cp;
 808         int ret;
 809
 810         pnt = strchr(str, '/');
 811
 812         /* If string doesn't contain `/' treat it as host route. */
 813         if (pnt == NULL) {
 814                 ret = inet_pton(AF_INET6, str, &p->prefix);
 815                 if (ret == 0)
 816                         return 0;
 817                 p->prefixlen = IPV6_MAX_BITLEN;
 818         } else {
 819                 int plen;
 820
 821                 cp = XMALLOC(MTYPE_TMP, (pnt - str) + 1);
 822                 strncpy(cp, str, pnt - str);
 823                 *(cp + (pnt - str)) = '\0';
 824                 ret = inet_pton(AF_INET6, cp, &p->prefix);
 825                 XFREE(MTYPE_TMP, cp);
 826                 if (ret == 0)
 827                         return 0;
 828                 plen = (u_char)atoi(++pnt);
 829                 if (plen > IPV6_MAX_BITLEN)
 830                         return 0;
 831                 p->prefixlen = plen;
 832         }
 833         p->family = AF_INET6;
 834
 835         return ret;
 836 }
 837
 838 /* Convert struct in6_addr netmask into integer.
 839  * FIXME return u_char as ip_maskleni() does. */
 840 int ip6_masklen(struct in6_addr netmask)
 841 {
 842         int len = 0;
 843         unsigned char val;
 844         unsigned char *pnt;
 845
 846         pnt = (unsigned char *)&netmask;
 847
 848         while ((*pnt == 0xff) && len < IPV6_MAX_BITLEN) {
 849                 len += 8;
 850                 pnt++;
 851         }
 852
 853         if (len < IPV6_MAX_BITLEN) {
 854                 val = *pnt;
 855                 while (val) {
 856                         len++;
 857                         val <<= 1;
 858                 }
 859         }
 860         return len;
 861 }
 862
 863 void masklen2ip6(const int masklen, struct in6_addr *netmask)
 864 {
 865         assert(masklen >= 0 && masklen <= IPV6_MAX_BITLEN);
 866         memcpy(netmask, maskbytes6 + masklen, sizeof(struct in6_addr));
 867 }
 868
 869 void apply_mask_ipv6(struct prefix_ipv6 *p)
 870 {
 871         u_char *pnt;
 872         int index;
 873         int offset;
 874
 875         index = p->prefixlen / 8;
 876
 877         if (index < 16) {
 878                 pnt = (u_char *)&p->prefix;
 879                 offset = p->prefixlen % 8;
 880
 881                 pnt[index] &= maskbit[offset];
 882                 index++;
 883
 884                 while (index < 16)
 885                         pnt[index++] = 0;
 886         }
 887 }
 888
 889 void apply_mask(struct prefix *p)
 890 {
 891         switch (p->family) {
 892         case AF_INET:
 893                 apply_mask_ipv4((struct prefix_ipv4 *)p);
 894                 break;
 895         case AF_INET6:
 896                 apply_mask_ipv6((struct prefix_ipv6 *)p);
 897                 break;
 898         default:
 899                 break;
 900         }
 901         return;
 902 }
 903
 904 /* Utility function of convert between struct prefix <=> union sockunion.
 905  * FIXME This function isn't used anywhere. */
 906 struct prefix *sockunion2prefix(const union sockunion *dest,
 907                                 const union sockunion *mask)
 908 {
 909         if (dest->sa.sa_family == AF_INET) {
 910                 struct prefix_ipv4 *p;
 911
 912                 p = prefix_ipv4_new();
 913                 p->family = AF_INET;
 914                 p->prefix = dest->sin.sin_addr;
 915                 p->prefixlen = ip_masklen(mask->sin.sin_addr);
 916                 return (struct prefix *)p;
 917         }
 918         if (dest->sa.sa_family == AF_INET6) {
 919                 struct prefix_ipv6 *p;
 920
 921                 p = prefix_ipv6_new();
 922                 p->family = AF_INET6;
 923                 p->prefixlen = ip6_masklen(mask->sin6.sin6_addr);
 924                 memcpy(&p->prefix, &dest->sin6.sin6_addr,
 925                        sizeof(struct in6_addr));
 926                 return (struct prefix *)p;
 927         }
 928         return NULL;
 929 }
 930
 931 /* Utility function of convert between struct prefix <=> union sockunion. */
 932 struct prefix *sockunion2hostprefix(const union sockunion *su,
 933                                     struct prefix *prefix)
 934 {
 935         if (su->sa.sa_family == AF_INET) {
 936                 struct prefix_ipv4 *p;
 937
 938                 p = prefix ? (struct prefix_ipv4 *)prefix : prefix_ipv4_new();
 939                 p->family = AF_INET;
 940                 p->prefix = su->sin.sin_addr;
 941                 p->prefixlen = IPV4_MAX_BITLEN;
 942                 return (struct prefix *)p;
 943         }
 944         if (su->sa.sa_family == AF_INET6) {
 945                 struct prefix_ipv6 *p;
 946
 947                 p = prefix ? (struct prefix_ipv6 *)prefix : prefix_ipv6_new();
 948                 p->family = AF_INET6;
 949                 p->prefixlen = IPV6_MAX_BITLEN;
 950                 memcpy(&p->prefix, &su->sin6.sin6_addr,
 951                        sizeof(struct in6_addr));
 952                 return (struct prefix *)p;
 953         }
 954         return NULL;
 955 }
 956
 957 void prefix2sockunion(const struct prefix *p, union sockunion *su)
 958 {
 959         memset(su, 0, sizeof(*su));
 960
 961         su->sa.sa_family = p->family;
 962         if (p->family == AF_INET)
 963                 su->sin.sin_addr = p->u.prefix4;
 964         if (p->family == AF_INET6)
 965                 memcpy(&su->sin6.sin6_addr, &p->u.prefix6,
 966                        sizeof(struct in6_addr));
 967 }
 968
 969 int prefix_blen(const struct prefix *p)
 970 {
 971         switch (p->family) {
 972         case AF_INET:
 973                 return IPV4_MAX_BYTELEN;
 974                 break;
 975         case AF_INET6:
 976                 return IPV6_MAX_BYTELEN;
 977                 break;
 978         case AF_ETHERNET:
 979                 return ETH_ALEN;
 980                 break;
 981         }
 982         return 0;
 983 }
 984
 985 /* Generic function for conversion string to struct prefix. */
 986 int str2prefix(const char *str, struct prefix *p)
 987 {
 988         int ret;
 989
 990         /* First we try to convert string to struct prefix_ipv4. */
 991         ret = str2prefix_ipv4(str, (struct prefix_ipv4 *)p);
 992         if (ret)
 993                 return ret;
 994
 995         /* Next we try to convert string to struct prefix_ipv6. */
 996         ret = str2prefix_ipv6(str, (struct prefix_ipv6 *)p);
 997         if (ret)
 998                 return ret;
 999
1000         /* Next we try to convert string to struct prefix_eth. */
1001         ret = str2prefix_eth(str, (struct prefix_eth *)p);
1002         if (ret)
1003                 return ret;
1004
1005         return 0;
1006 }
1007
1008 static const char *prefixevpn2str(const struct prefix *p, char *str, int size)
1009 {
1010         u_char family;
1011         char buf[PREFIX2STR_BUFFER];
1012         char buf2[ETHER_ADDR_STRLEN];
1013
1014         if (p->u.prefix_evpn.route_type == 2) {
1015                 if (IS_EVPN_PREFIX_IPADDR_NONE((struct prefix_evpn *)p))
1016                         snprintf(str, size, "[%d]:[%s]/%d",
1017                                  p->u.prefix_evpn.route_type,
1018                                  prefix_mac2str(&p->u.prefix_evpn.mac, buf2,
1019                                                 sizeof(buf2)),
1020                                  p->prefixlen);
1021                 else {
1022                         family = IS_EVPN_PREFIX_IPADDR_V4(
1023                                          (struct prefix_evpn *)p)
1024                                          ? AF_INET
1025                                          : AF_INET6;
1026                         snprintf(str, size, "[%d]:[%s]:[%s]/%d",
1027                                  p->u.prefix_evpn.route_type,
1028                                  prefix_mac2str(&p->u.prefix_evpn.mac, buf2,
1029                                                 sizeof(buf2)),
1030                                  inet_ntop(family, &p->u.prefix_evpn.ip.ip.addr,
1031                                            buf, PREFIX2STR_BUFFER),
1032                                  p->prefixlen);
1033                 }
1034         } else if (p->u.prefix_evpn.route_type == 3) {
1035                 family = IS_EVPN_PREFIX_IPADDR_V4((struct prefix_evpn *)p)
1036                                  ? AF_INET
1037                                  : AF_INET6;
1038                 snprintf(str, size, "[%d]:[%s]/%d", p->u.prefix_evpn.route_type,
1039                          inet_ntop(family, &p->u.prefix_evpn.ip.ip.addr, buf,
1040                                    PREFIX2STR_BUFFER),
1041                          p->prefixlen);
1042         } else if (p->u.prefix_evpn.route_type == 5) {
1043                 family = IS_EVPN_PREFIX_IPADDR_V4((struct prefix_evpn *)p)
1044                                  ? AF_INET
1045                                  : AF_INET6;
1046                 snprintf(str, size, "[%d]:[%u][%s]/%d",
1047                          p->u.prefix_evpn.route_type, p->u.prefix_evpn.eth_tag,
1048                          inet_ntop(family, &p->u.prefix_evpn.ip.ip.addr, buf,
1049                                    PREFIX2STR_BUFFER),
1050                          p->prefixlen);
1051         } else {
1052                 sprintf(str, "Unsupported EVPN route type %d",
1053                          p->u.prefix_evpn.route_type);
1054         }
1055
1056         return str;
1057 }
1058
1059 const char *prefix2str(union prefixconstptr pu, char *str, int size)
1060 {
1061         const struct prefix *p = pu.p;
1062         char buf[PREFIX2STR_BUFFER];
1063
1064         switch (p->family) {
1065         case AF_INET:
1066         case AF_INET6:
1067                 snprintf(str, size, "%s/%d", inet_ntop(p->family, &p->u.prefix,
1068                                                        buf, PREFIX2STR_BUFFER),
1069                          p->prefixlen);
1070                 break;
1071
1072         case AF_ETHERNET:
1073                 snprintf(str, size, "%s/%d",
1074                          prefix_mac2str(&p->u.prefix_eth, buf, sizeof(buf)),
1075                          p->prefixlen);
1076                 break;
1077
1078         case AF_EVPN:
1079                 prefixevpn2str(p, str, size);
1080                 break;
1081
1082         default:
1083                 sprintf(str, "UNK prefix");
1084                 break;
1085         }
1086
1087         return str;
1088 }
1089
1090 struct prefix *prefix_new()
1091 {
1092         struct prefix *p;
1093
1094         p = XCALLOC(MTYPE_PREFIX, sizeof *p);
1095         return p;
1096 }
1097
1098 /* Free prefix structure. */
1099 void prefix_free(struct prefix *p)
1100 {
1101         XFREE(MTYPE_PREFIX, p);
1102 }
1103
1104 /* Utility function.  Check the string only contains digit
1105  * character.
1106  * FIXME str.[c|h] would be better place for this function. */
1107 int all_digit(const char *str)
1108 {
1109         for (; *str != '\0'; str++)
1110                 if (!isdigit((int)*str))
1111                         return 0;
1112         return 1;
1113 }
1114
1115 /* Utility function to convert ipv4 prefixes to Classful prefixes */
1116 void apply_classful_mask_ipv4(struct prefix_ipv4 *p)
1117 {
1118
1119         u_int32_t destination;
1120
1121         destination = ntohl(p->prefix.s_addr);
1122
1123         if (p->prefixlen == IPV4_MAX_PREFIXLEN)
1124                 ;
1125         /* do nothing for host routes */
1126         else if (IN_CLASSC(destination)) {
1127                 p->prefixlen = 24;
1128                 apply_mask_ipv4(p);
1129         } else if (IN_CLASSB(destination)) {
1130                 p->prefixlen = 16;
1131                 apply_mask_ipv4(p);
1132         } else {
1133                 p->prefixlen = 8;
1134                 apply_mask_ipv4(p);
1135         }
1136 }
1137
1138 in_addr_t ipv4_network_addr(in_addr_t hostaddr, int masklen)
1139 {
1140         struct in_addr mask;
1141
1142         masklen2ip(masklen, &mask);
1143         return hostaddr & mask.s_addr;
1144 }
1145
1146 in_addr_t ipv4_broadcast_addr(in_addr_t hostaddr, int masklen)
1147 {
1148         struct in_addr mask;
1149
1150         masklen2ip(masklen, &mask);
1151         return (masklen != IPV4_MAX_PREFIXLEN - 1) ?
1152                                                    /* normal case */
1153                        (hostaddr | ~mask.s_addr)
1154                                                    :
1155                                                    /* special case for /31 */
1156                        (hostaddr ^ ~mask.s_addr);
1157 }
1158
1159 /* Utility function to convert ipv4 netmask to prefixes
1160    ex.) "1.1.0.0" "255.255.0.0" => "1.1.0.0/16"
1161    ex.) "1.0.0.0" NULL => "1.0.0.0/8"                   */
1162 int netmask_str2prefix_str(const char *net_str, const char *mask_str,
1163                            char *prefix_str)
1164 {
1165         struct in_addr network;
1166         struct in_addr mask;
1167         u_char prefixlen;
1168         u_int32_t destination;
1169         int ret;
1170
1171         ret = inet_aton(net_str, &network);
1172         if (!ret)
1173                 return 0;
1174
1175         if (mask_str) {
1176                 ret = inet_aton(mask_str, &mask);
1177                 if (!ret)
1178                         return 0;
1179
1180                 prefixlen = ip_masklen(mask);
1181         } else {
1182                 destination = ntohl(network.s_addr);
1183
1184                 if (network.s_addr == 0)
1185                         prefixlen = 0;
1186                 else if (IN_CLASSC(destination))
1187                         prefixlen = 24;
1188                 else if (IN_CLASSB(destination))
1189                         prefixlen = 16;
1190                 else if (IN_CLASSA(destination))
1191                         prefixlen = 8;
1192                 else
1193                         return 0;
1194         }
1195
1196         sprintf(prefix_str, "%s/%d", net_str, prefixlen);
1197
1198         return 1;
1199 }
1200
1201 /* Utility function for making IPv6 address string. */
1202 const char *inet6_ntoa(struct in6_addr addr)
1203 {
1204         static char buf[INET6_ADDRSTRLEN];
1205
1206         inet_ntop(AF_INET6, &addr, buf, INET6_ADDRSTRLEN);
1207         return buf;
1208 }
1209
1210 /* converts to internal representation of mac address
1211  * returns 1 on success, 0 otherwise
1212  * format accepted: AA:BB:CC:DD:EE:FF
1213  * if mac parameter is null, then check only
1214  */
1215 int prefix_str2mac(const char *str, struct ethaddr *mac)
1216 {
1217         unsigned int a[6];
1218         int i;
1219
1220         if (!str)
1221                 return 0;
1222
1223         if (sscanf(str, "%2x:%2x:%2x:%2x:%2x:%2x", a + 0, a + 1, a + 2, a + 3,
1224                    a + 4, a + 5)
1225             != 6) {
1226                 /* error in incoming str length */
1227                 return 0;
1228         }
1229         /* valid mac address */
1230         if (!mac)
1231                 return 1;
1232         for (i = 0; i < 6; ++i)
1233                 mac->octet[i] = a[i] & 0xff;
1234         return 1;
1235 }
1236
1237 char *prefix_mac2str(const struct ethaddr *mac, char *buf, int size)
1238 {
1239         char *ptr;
1240
1241         if (!mac)
1242                 return NULL;
1243         if (!buf)
1244                 ptr = (char *)XMALLOC(MTYPE_TMP,
1245                                       ETHER_ADDR_STRLEN * sizeof(char));
1246         else {
1247                 assert(size >= ETHER_ADDR_STRLEN);
1248                 ptr = buf;
1249         }
1250         snprintf(ptr, (ETHER_ADDR_STRLEN), "%02x:%02x:%02x:%02x:%02x:%02x",
1251                  (uint8_t)mac->octet[0], (uint8_t)mac->octet[1],
1252                  (uint8_t)mac->octet[2], (uint8_t)mac->octet[3],
1253                  (uint8_t)mac->octet[4], (uint8_t)mac->octet[5]);
1254         return ptr;
1255 }
1256
1257 unsigned prefix_hash_key(void *pp)
1258 {
1259         struct prefix copy;
1260
1261         /* make sure *all* unused bits are zero, particularly including
1262          * alignment /
1263          * padding and unused prefix bytes. */
1264         memset(&copy, 0, sizeof(copy));
1265         prefix_copy(&copy, (struct prefix *)pp);
1266         return jhash(&copy, offsetof(struct prefix, u.prefix)
1267                      + PSIZE(copy.prefixlen), 0x55aa5a5a);
1268 }