modernize backfire 10.03 so it can be operational again
[openwrt-10.03/.git] / package / quagga / not-patches / patches-pgbgp / 160-pgbgp.patch
1 From: Josh Karlin <karlinjf@cs.unm.edu>
2 Date: Mon, 18 Aug 2008 13:17:21 +0000 (+0100)
3 Subject: [bgp] Add support for Pretty-Good BGP
4 X-Git-Url: http://git.ozo.com/?p=quagga-pgbg.git;a=commitdiff_plain;h=c2ee55705cad607f4b86ff143f7af92d538dc946
5
6 [bgp] Add support for Pretty-Good BGP
7
8 2008-7-7 Josh Karlin <karlinjf@cs.unm.edu>
9
10         * bgpd/bgp_pgbgp.c: Added file
11         * bgpd/bgp_pgbgp.h: Added file
12         * bgpd/Makefile.am: Added bgp_pgbgp.h and bgp_pgbgp.c
13         * bgpd/bgp_aspath.h: Externed the hash of as paths (ashash)
14         * bgpd/bgp_route.c: . Added PGBGP depref check to decision process.
15                             . Informs PGBGP of new updates and selected routes
16                             . Added anomaly status for show ip bgp
17                             . Added PGBGP commands
18         * bgpd/bgp_route.h: Added suspicious route flags
19         * bgpd/bgp_table.h: Added PGBGP history pointer to struct bgp_node
20         * bgpd/bgpd.h:      Defined BGP_CONFIG_PGBGP
21         * lib/hash.c:       Added "hash_iterate_until" to be able to break out
22         * lib/hash.h:       Definition for "hash_iterate_until"
23         * lib/memtypes.c:   Added PGBGP memory types
24 ---
25
26 --- a/bgpd/Makefile.am
27 +++ b/bgpd/Makefile.am
28 @@ -15,14 +15,14 @@ libbgp_a_SOURCES = \
29         bgp_debug.c bgp_route.c bgp_zebra.c bgp_open.c bgp_routemap.c \
30         bgp_packet.c bgp_network.c bgp_filter.c bgp_regex.c bgp_clist.c \
31         bgp_dump.c bgp_snmp.c bgp_ecommunity.c bgp_mplsvpn.c bgp_nexthop.c \
32 -       bgp_damp.c bgp_table.c bgp_advertise.c bgp_vty.c bgp_mpath.c
33 +       bgp_damp.c bgp_table.c bgp_advertise.c bgp_vty.c bgp_mpath.c bgp_pgbgp.c
34  
35  noinst_HEADERS = \
36         bgp_aspath.h bgp_attr.h bgp_community.h bgp_debug.h bgp_fsm.h \
37         bgp_network.h bgp_open.h bgp_packet.h bgp_regex.h bgp_route.h \
38         bgpd.h bgp_filter.h bgp_clist.h bgp_dump.h bgp_zebra.h \
39         bgp_ecommunity.h bgp_mplsvpn.h bgp_nexthop.h bgp_damp.h bgp_table.h \
40 -       bgp_advertise.h bgp_snmp.h bgp_vty.h bgp_mpath.h
41 +       bgp_advertise.h bgp_snmp.h bgp_vty.h bgp_mpath.h bgp_pgbgp.h
42  
43  bgpd_SOURCES = bgp_main.c
44  bgpd_LDADD = libbgp.a ../lib/libzebra.la @LIBCAP@ @LIBM@
45 --- /dev/null
46 +++ b/bgpd/bgp_pgbgp.c
47 @@ -0,0 +1,2401 @@
48 +/* 
49 +   BGP Pretty Good BGP
50 +   Copyright (C) 2008 University of New Mexico (Josh Karlin)
51 +
52 +This file is part of GNU Zebra.
53 +
54 +GNU Zebra is free software; you can redistribute it and/or modify it
55 +under the terms of the GNU General Public License as published by the
56 +Free Software Foundation; either version 2, or (at your option) any
57 +later version.
58 +
59 +GNU Zebra is distributed in the hope that it will be useful, but
60 +WITHOUT ANY WARRANTY; without even the implied warranty of
61 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
62 +General Public License for more details.
63 +
64 +You should have received a copy of the GNU General Public License
65 +along with GNU Zebra; see the file COPYING.  If not, write to the Free
66 +Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
67 +02111-1307, USA. 
68 +*/
69 +
70 +/*
71 +  Quagga based Pretty Good BGP:
72 +
73 +  Summary 
74 +  ------- 
75 +  Pretty Good BGP (PGBGP) is a soft security enhancement to BGP.
76 +  It uses independently collected (therefore completely distributed)
77 +  historical routing information to determine network topology and
78 +  prefix ownership.  Abberations to the historical database are considered
79 +  anomalous and avoided when possible.
80 +
81 +  What PGBGP can protect against: prefix hijacks, sub-prefix hijacks, and
82 +  spoofed edges.
83 +
84 +  Further reading is available at http://cs.unm.edu/~karlinjf/pgbgp/
85 +
86 +  Route updates are forwarded to PGBGP, which determines if the route
87 +  is anomalous.  Anomalous routes are flagged as suspicious and
88 +  avoided where feasible for 24 hours.  If the anomalous
89 +  characteristic is still in the RIB after 24 hours, consider it valid
90 +  and enter it into the normal database.
91 +
92 +  Cases for anomalous routes
93 +  --------------------------
94 +  case 1) New origin AS - prefix pair (one not recently seen in the RIB):
95 +     response) label the route with BGP_INFO_SUSPICIOUS_O and avoid for 24 hours if possible
96 +
97 +  case 2) New edge in path (one not recently seen in the RIB): 
98 +     response) label the route with BGP_INFO_SUSPICIOUS_E and avoid for 24 hours
99 +               if possible
100 +
101 +  case 3) New prefix that is a sub-prefix of a prefix in recent history 
102 +          and that path differs from the current less-specific's path
103 +     response) label the sub-prefix routes with BGP_INFO_IGNORED_P and 
104 +               prevent it from entering FIB for 24 hours
105 +     response) label the super-net routes from the same next-hop as BGP_INFO_SUSPICIOUS_P 
106 +               and try to avoid it for 24 hours if possible
107 +     response) while no super-net route is selected, remove the BGP_INFO_IGNORED_P flags
108 +  
109 +
110 +  Normal Database (history)
111 +  -------------------------
112 +  Recently Seen) A route characteristic (edge, prefix/origin pair, prefix) 
113 +                 that has resided within the RIB within the last X hours 
114 +                where X is user defined for each characteristic.
115 +  Storage) Prefix and Origin history are stored in bgp_node structs with the
116 +           "hist" pointer. 
117 +          Edge information is stored in a separate hash table, where the edge
118 +          is the key to the hash.
119 +  Updates) The history's primary function is the keep track of when each route 
120 +           characteristic was last seen.  For each route announcement, update 
121 +           the history's 'last seen' time.  Periodically run the garbage collector 
122 +          which updates 'last seen' times for objects currently in the RIB.
123 +  
124 +  Garbage Collection
125 +  ------------------
126 +  Periodically the garbage collector (gc) is called to remove stale history 
127 +  information and update the lastSeen time of objects that reside in the RIB 
128 +  at the time of collection.  This is relatively expensive as it walks
129 +  the RIB as well as the list of AS paths.
130 +
131 +  What is removed) Objects that have not been seen in the RIB within a user-defined
132 +                   time.
133 +                  Suspicious objcets that are 24 hours old that have not been in the RIB
134 +                  since the last collection.
135 +  
136 +  Reuse Priority Queue
137 +  --------------------
138 +  After 24 hours, routes that are flagged as suspicious have the flags removed.  
139 +  This is not run on a timer.  Instead, for each update that PGBGP is informed of,
140 +  it checks the reuse queue to determine if any routes need to be updated.
141 +
142 +*/
143 +
144 +
145 +/*
146 +  Things that must be ensured:
147 +  . GC updates lastSeen so it must be called at least twice as often as the lowest BUFFER_TIME
148 +  . GC should be called at least twice per day
149 +  . Delay times must be shorter than history window lengths
150 +*/
151 +
152 +
153 +/*
154 +  Changes made to original PGBGP thinking
155 +  . Don't check for things in the RIB all of the time, periodically 
156 +    update the lastSeen values and just use lastSeen
157 +*/
158 +
159 +/*
160 +  Changes made to original protocol
161 +  . sub-prefixes are only ignored while the super-net has a selected 
162 +    route and it's non-anomalous (not to a neighbor that announced 
163 +    the sub-prefix)
164 +  
165 +  . At point of reuse, don't delete the item if it's not in the RIB. 
166 +    delete it if it hasn't been in the RIB since the last storage.  
167 +    This saves a lot of processing time for new edges
168 +
169 +  . Changed heuristic from "if new sub-prefix and trusted AS on path 
170 +    then it's okay" to  "if new sub-prefix and same path is used to reach 
171 +    super-prefix, then it's okay".  Might be better to change to "if old 
172 +    path is prefix of new path, then okay"
173 +*/
174 +
175 +#include <zebra.h>
176 +#include <math.h>
177 +
178 +#include "prefix.h"
179 +#include "memory.h"
180 +#include "command.h"
181 +#include "log.h"
182 +#include "pqueue.h"
183 +#include "table.h"
184 +#include "hash.h"
185 +#include "str.h"
186 +
187 +#include "bgpd/bgpd.h"
188 +#include "bgpd/bgp_aspath.h"
189 +#include "bgpd/bgp_pgbgp.h"
190 +#include "bgpd/bgp_table.h"
191 +#include "bgpd/bgp_route.h"
192 +#include "bgpd/bgp_attr.h"
193 +#include "bgpd/bgp_advertise.h"
194 +
195 +
196 +#define true 1
197 +#define false 0
198 +
199 +struct hash * ashash;
200 +
201 +static void *edge_hash_alloc (void *arg);
202 +static unsigned int edge_key_make (void *p);
203 +static int edge_cmp (const void *arg1, const void *args);
204 +
205 +// Helper Functions
206 +static struct bgp_pgbgp_pathSet bgp_pgbgp_pathOrigin (struct aspath *);
207 +static int bgp_pgbgp_pathLength (struct aspath *asp);
208 +static int bgp_pgbgp_gc (struct bgp_table *);
209 +static int bgp_pgbgp_clean (struct bgp_table *);
210 +static int bgp_pgbgp_reuse (time_t);
211 +static struct bgp_node *findSuper (struct bgp_table *table, struct prefix *p,
212 +                            time_t t_now);
213 +static int bgp_pgbgp_store (struct bgp_table *table);
214 +static int bgp_pgbgp_restore (void);
215 +static struct bgp_info *bgp_pgbgp_selected (struct bgp_node *node);
216 +static int originInRIB (struct bgp_node *node, struct bgp_pgbgp_origin *origin);
217 +static int prefixInRIB (struct bgp_node *node, struct bgp_pgbgp_prefix *prefix);
218 +static int edgeInRIB (struct bgp_pgbgp_edge *e);
219 +
220 +// MOAS Functions
221 +static void bgp_pgbgp_logOriginAnomaly (as_t asn, struct bgp_node *rn,
222 +                                 struct attr *);
223 +static int bgp_pgbgp_reuseOrigin (struct bgp_pgbgp_r_origin);
224 +static void bgp_pgbgp_cleanHistTable (struct bgp_table *);
225 +static int bgp_pgbgp_garbageCollectHistTable (struct bgp_table *);
226 +static void bgp_pgbgp_storeHistTable (struct bgp_table *table, FILE * file);
227 +static int bgp_pgbgp_updateOrigin (struct bgp_pgbgp_hist *, struct bgp_info *,
228 +                            struct attr *, struct bgp_node *, time_t, int);
229 +
230 +
231 +// Sub-Prefix Hijack Detector Functions
232 +static int bgp_pgbgp_shouldIgnore (struct bgp_node *super, struct bgp_info *selected);
233 +static void bgp_pgbgp_logSubprefixAnomaly (as_t asn, struct bgp_node *rn,
234 +                                    struct attr *, struct bgp_node *super);
235 +static int bgp_pgbgp_reusePrefix (struct bgp_pgbgp_r_prefix);
236 +static int bgp_pgbgp_updatePrefix (struct bgp_pgbgp_hist *hist, struct bgp_node *,
237 +                            struct bgp_info *, struct attr *,
238 +                            struct bgp_node *, time_t, int);
239 +
240 +
241 +// Spoofed Edge Detector Functions
242 +static void bgp_pgbgp_cleanEdges (void);
243 +static void bgp_pgbgp_logEdgeAnomaly (struct bgp_node *rn, struct attr *,
244 +                               struct edge *edge);
245 +static int bgp_pgbgp_reuseEdge (struct bgp_pgbgp_r_edge);
246 +static void bgp_pgbgp_storeEdges (struct bgp_table *, FILE *);
247 +static int bgp_pgbgp_garbageCollectEdges (struct bgp_table *);
248 +static int bgp_pgbgp_updateEdge (struct bgp_pgbgp_hist *hist, struct bgp_info *,
249 +                          struct attr *, struct bgp_node *, time_t, int);
250 +static int bgp_pgbgp_restoreEdge (FILE * file);
251 +static void bgp_pgbgp_storeEdges (struct bgp_table *table, FILE * file);
252 +
253 +
254 +
255 +// New Peer Detector Functions
256 +static int bgp_pgbgp_updatePeer (struct bgp_info *binfo, time_t now);
257 +
258 +
259 +/* --------------- Global Variables ------------------ */
260 +struct bgp_pgbgp_config bgp_pgbgp_cfg;
261 +struct bgp_pgbgp_config *pgbgp = &bgp_pgbgp_cfg;
262 +/*! --------------- Global Variables ------------------ !*/
263 +
264 +/* --------------- VTY (others exist in bgp_route.c)  ------------------ */
265 +
266 +struct nsearch
267 +{
268 +  struct vty *pvty;
269 +  time_t time;
270 +  as_t asn;
271 +};
272 +
273 +static void
274 +edge_neighbor_iterator (struct hash_backet *backet, struct nsearch *pns)
275 +{
276 +  struct bgp_pgbgp_edge *hedge = backet->data;
277 +  if ((hedge->e.a == pns->asn || hedge->e.b == pns->asn)
278 +      && hedge->e.a != hedge->e.b)
279 +    {
280 +      struct vty *vty = pns->pvty;
281 +      if (hedge->deprefUntil > pns->time)
282 +        vty_out (pns->pvty, "Untrusted: %d -- %d%s", hedge->e.a, hedge->e.b,
283 +                 VTY_NEWLINE);
284 +      else
285 +        vty_out (pns->pvty, "Trusted: %d -- %d%s", hedge->e.a, hedge->e.b,
286 +                 VTY_NEWLINE);
287 +    }
288 +}
289 +
290 +static int
291 +bgp_pgbgp_stats_neighbors (struct vty *vty, afi_t afi, safi_t safi, as_t asn)
292 +{
293 +  struct nsearch ns;
294 +  ns.pvty = vty;
295 +  ns.time = time (NULL);
296 +  ns.asn = asn;
297 +
298 +  hash_iterate (pgbgp->edgeT,
299 +                (void (*)(struct hash_backet *, void *))
300 +                edge_neighbor_iterator, &ns);
301 +  return CMD_SUCCESS;
302 +}
303 +
304 +static int
305 +bgp_pgbgp_stats_origins (struct vty *vty, afi_t afi, safi_t safi,
306 +                         const char *prefix)
307 +{
308 +  struct bgp *bgp;
309 +  struct bgp_table *table;
310 +  time_t t_now = time (NULL);
311 +  bgp = bgp_get_default ();
312 +  if (bgp == NULL)
313 +    return CMD_WARNING;
314 +  if (bgp->rib == NULL)
315 +    return CMD_WARNING;
316 +  table = bgp->rib[afi][safi];
317 +  if (table == NULL)
318 +    return CMD_WARNING;
319 +
320 +  struct prefix p;
321 +  str2prefix (prefix, &p);
322 +  struct bgp_node *rn = bgp_node_match (table, &p);
323 +  vty_out (vty, "%s%s", prefix, VTY_NEWLINE);
324 +  if (rn)
325 +    {
326 +      if (rn->hist)
327 +        {
328 +          for (struct bgp_pgbgp_origin * cur = rn->hist->o; cur != NULL;
329 +               cur = cur->next)
330 +            {
331 +              if (cur->deprefUntil > t_now)
332 +                vty_out (vty, "Untrusted Origin AS: %d%s", cur->originAS,
333 +                         VTY_NEWLINE);
334 +              else
335 +                vty_out (vty, "Trusted Origin AS: %d%s", cur->originAS,
336 +                         VTY_NEWLINE);
337 +            }
338 +        }
339 +      bgp_unlock_node (rn);
340 +    }
341 +  return CMD_SUCCESS;
342 +}
343 +
344 +static int
345 +bgp_pgbgp_stats (struct vty *vty, afi_t afi, safi_t safi)
346 +{
347 +  struct bgp *bgp;
348 +  struct bgp_table *table;
349 +
350 +
351 +  bgp = bgp_get_default ();
352 +  if (bgp == NULL)
353 +    return CMD_WARNING;
354 +  if (bgp->rib == NULL)
355 +    return CMD_WARNING;
356 +  table = bgp->rib[afi][safi];
357 +  if (table == NULL)
358 +    return CMD_WARNING;
359 +
360 +  //    bgp_pgbgp_store(table);
361 +
362 +  // Print out the number of anomalous routes
363 +  int anomalous = 0;
364 +  int routes = 0;
365 +  int num_selected = 0;
366 +  int num_origin = 0;
367 +  int num_super = 0;
368 +  int num_ignored = 0;
369 +  int num_edge = 0;
370 +
371 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
372 +       rn = bgp_route_next (rn))
373 +    {
374 +      for (struct bgp_info * ri = rn->info; ri; ri = ri->next)
375 +        {
376 +          routes += 1;
377 +          if (ANOMALOUS (ri->flags))
378 +            {
379 +              anomalous += 1;
380 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED))
381 +                num_selected += 1;
382 +
383 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O))
384 +                num_origin += 1;
385 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_E))
386 +                num_edge += 1;
387 +              if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P))
388 +                num_super += 1;
389 +              if (CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
390 +                num_ignored += 1;
391 +            }
392 +        }
393 +    }
394 +
395 +  vty_out (vty, "%-30s: %10d%s", "Routes in the RIB", routes, VTY_NEWLINE);
396 +  vty_out (vty, "%-30s: %10d%s", "Anomalous routes in RIB", anomalous,
397 +           VTY_NEWLINE);
398 +  vty_out (vty, "%-30s: %10d%s", "Selected anomalous routes", num_selected,
399 +           VTY_NEWLINE);
400 +  vty_out (vty, "-----------------------------%s", VTY_NEWLINE);
401 +  vty_out (vty, "%-30s: %10d%s", "Routes with anomalous origins", num_origin,
402 +           VTY_NEWLINE);
403 +  vty_out (vty, "%-30s: %10d%s", "Routes with anomalous edges", num_edge,
404 +           VTY_NEWLINE);
405 +  vty_out (vty, "%-30s: %10d%s", "Routes ignored for sub-prefix", num_ignored,
406 +           VTY_NEWLINE);
407 +  vty_out (vty, "%-30s: %10d%s", "Less specific routes to avoid", num_super,
408 +           VTY_NEWLINE);
409 +  /*
410 +     vty_out (vty, "There are %d routes in the RIB.%s", routes, VTY_NEWLINE); 
411 +     vty_out (vty, "%d are anomalous.%s", anomalous, VTY_NEWLINE);
412 +     vty_out (vty, "%d anomalous routes are selected.%s", num_selected, VTY_NEWLINE);
413 +     vty_out (vty, "%s", VTY_NEWLINE);
414 +     vty_out (vty, "Anomaly breakdown:%s", VTY_NEWLINE);
415 +     vty_out (vty, "%d contain anomalous origins%s", num_origin, VTY_NEWLINE);
416 +     vty_out (vty, "%d contain anomalous edges.%s", num_edge, VTY_NEWLINE);
417 +     vty_out (vty, "%d are for ignored sub-prefixes.%s", num_ignored, VTY_NEWLINE);
418 +     vty_out (vty, "%d are super-net routes through peers that announced anomalous sub-prefixes.%s", num_super, VTY_NEWLINE);
419 +   */
420 +  return CMD_SUCCESS;
421 +}
422 +
423 +
424 +DEFUN (show_ip_bgp_pgbgp,
425 +       show_ip_bgp_pgbgp_cmd,
426 +       "show ip bgp pgbgp",
427 +       SHOW_STR IP_STR BGP_STR "Display PGBGP statistics\n")
428 +{
429 +  return bgp_pgbgp_stats (vty, AFI_IP, SAFI_UNICAST);
430 +}
431 +
432 +DEFUN (show_ip_bgp_pgbgp_neighbors,
433 +       show_ip_bgp_pgbgp_neighbors_cmd,
434 +       "show ip bgp pgbgp neighbors WORD",
435 +       SHOW_STR
436 +       IP_STR
437 +       BGP_STR
438 +       "BGP pgbgp\n"
439 +       "BGP pgbgp neighbors\n" "ASN whos neighbors should be displayed\n")
440 +{
441 +  return bgp_pgbgp_stats_neighbors (vty, AFI_IP, SAFI_UNICAST,
442 +                                    atoi (argv[0]));
443 +}
444 +
445 +DEFUN (show_ip_bgp_pgbgp_origins,
446 +       show_ip_bgp_pgbgp_origins_cmd,
447 +       "show ip bgp pgbgp origins A.B.C.D/M",
448 +       SHOW_STR
449 +       IP_STR
450 +       BGP_STR
451 +       "BGP pgbgp\n"
452 +       "BGP pgbgp neighbors\n" "Prefix to look up origin ASes of\n")
453 +{
454 +  return bgp_pgbgp_stats_origins (vty, AFI_IP, SAFI_UNICAST, argv[0]);
455 +}
456 +
457 +
458 +
459 +
460 +/*! --------------- VTY (others exist in bgp_route.c)  ------------------ !*/
461 +
462 +
463 +
464 +
465 +
466 +
467 +
468 +/* --------------- Helper Functions ------------------ */
469 +/*
470 +  If the origin hasn't been seen/verified lately, look for it in the RIB
471 +*/
472 +int
473 +originInRIB (struct bgp_node *node, struct bgp_pgbgp_origin *origin)
474 +{
475 +  for (struct bgp_info * ri = node->info; ri; ri = ri->next)
476 +    {
477 +      struct bgp_pgbgp_pathSet pathOrigins;
478 +      pathOrigins = bgp_pgbgp_pathOrigin (ri->attr->aspath);
479 +      for (int i = 0; i < pathOrigins.length; ++i)
480 +        {
481 +          if (pathOrigins.ases[i] == origin->originAS)
482 +            {
483 +              return true;
484 +            }
485 +        }
486 +    }
487 +  return false;
488 +}
489 +
490 +
491 +/*
492 +  If the prefix hasn't been seen/verified lately, look for it in the RIB
493 +*/
494 +int
495 +prefixInRIB (struct bgp_node *node, struct bgp_pgbgp_prefix *prefix)
496 +{
497 +  if (node->info)
498 +    return true;
499 +  return false;
500 +}
501 +
502 +static int
503 +edge_inRIB_iterator (struct hash_backet *backet, struct bgp_pgbgp_edge *hedge)
504 +{
505 +  struct aspath *p = backet->data;
506 +  char first = true;
507 +  struct edge curEdge;
508 +  curEdge.a = 0;
509 +  curEdge.b = 0;
510 +
511 +  struct assegment *seg;
512 +
513 +  for (seg = p->segments; seg; seg = seg->next)
514 +    {
515 +      for (int i = 0; i < seg->length; i++)
516 +        {
517 +          curEdge.a = curEdge.b;
518 +          curEdge.b = seg->as[i];
519 +          if (first)
520 +            {
521 +              first = false;
522 +              continue;
523 +            }
524 +          // Is this the edge we're looking for?
525 +          if (curEdge.a == hedge->e.a && curEdge.b == hedge->e.b)
526 +            {
527 +              hedge->lastSeen = time (NULL);
528 +              return false;
529 +            }
530 +        }
531 +    }
532 +
533 +  return true;
534 +}
535 +
536 +/*
537 +  If the edge hasn't been seen/verified lately, look for it in the AS path list
538 +  This function is expensive, use sparingly
539 +*/
540 +int
541 +edgeInRIB (struct bgp_pgbgp_edge *e)
542 +{
543 +  int completed;
544 +  completed = hash_iterate_until (ashash,
545 +                                  (int (*)(struct hash_backet *, void *))
546 +                                  edge_inRIB_iterator, e);
547 +  if (completed)
548 +    return false;
549 +
550 +  return true;
551 +}
552 +
553 +
554 +
555 +/*
556 +  Return the selected route for the given route node
557 + */
558 +
559 +struct bgp_info *
560 +bgp_pgbgp_selected (struct bgp_node *node)
561 +{
562 +  for (struct bgp_info * ri = node->info; ri; ri = ri->next)
563 +    {
564 +      if (CHECK_FLAG (ri->flags, BGP_INFO_SELECTED))
565 +        return ri;
566 +    }
567 +  return NULL;
568 +}
569 +
570 +static int
571 +reuse_cmp (void *node1, void *node2)
572 +{
573 +  struct bgp_pgbgp_reuse *a;
574 +  struct bgp_pgbgp_reuse *b;
575 +  a = (struct bgp_pgbgp_reuse *) node1;
576 +  b = (struct bgp_pgbgp_reuse *) node2;
577 +  return a->deprefUntil - b->deprefUntil;
578 +}
579 +
580 +int
581 +bgp_pgbgp_pathLength (struct aspath *asp)
582 +{
583 +  struct assegment *seg;
584 +  if ((asp == NULL) || (asp->segments == NULL))
585 +    return 0;
586 +  int count = 0;
587 +  seg = asp->segments;
588 +  while (seg->next != NULL)
589 +    {
590 +      count += seg->length;
591 +      seg = seg->next;
592 +    }
593 +  return count;
594 +}
595 +
596 +
597 +
598 +/* Find the origin(s) of the path
599 +   All ASes in the final set are considered origins */
600 +static struct bgp_pgbgp_pathSet
601 +bgp_pgbgp_pathOrigin (struct aspath *asp)
602 +{
603 +  struct assegment *seg, *last;
604 +  struct bgp_pgbgp_pathSet tmp;
605 +  tmp.length = 0;
606 +  tmp.ases = NULL;
607 +
608 +  assert (asp != NULL && asp->segments != NULL);
609 +
610 +  /*    if ( (asp == NULL) || (asp->segments == NULL) )
611 +     return tmp;
612 +   */
613 +  seg = asp->segments;
614 +  last = NULL;
615 +  while (seg->next != NULL)
616 +    {
617 +      if (seg->type != AS_SET && seg->type != AS_CONFED_SET)
618 +        last = seg;
619 +      seg = seg->next;
620 +    }
621 +
622 +  if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
623 +    seg = last;
624 +
625 +  assert (seg);
626 +  tmp.length = 1;
627 +  tmp.ases = &seg->as[seg->length - 1];
628 +
629 +  /*
630 +     if (seg->type == AS_SET || seg->type == AS_CONFED_SET)
631 +     {
632 +     tmp.length = seg->length;
633 +     tmp.ases = seg->as;
634 +     }
635 +     else
636 +     {
637 +     tmp.length = 1;
638 +     tmp.ases = &seg->as[seg->length - 1];
639 +     }
640 +   */
641 +  assert (tmp.length >= 1);
642 +  return tmp;
643 +  //    return seg->as[seg->length-1];
644 +}
645 +
646 +int
647 +bgp_pgbgp_reuse (time_t t_now)
648 +{
649 +
650 +  struct bgp_pgbgp_reuse *cur = NULL;
651 +
652 +  while (pgbgp->rq_size > 0)
653 +    {
654 +      cur = pqueue_dequeue (pgbgp->reuse_q);
655 +      pgbgp->rq_size -= 1;
656 +
657 +      // Is the next item ready to be reused?
658 +      if (t_now < cur->deprefUntil)
659 +        {
660 +          pqueue_enqueue (cur, pgbgp->reuse_q);
661 +          pgbgp->rq_size += 1;
662 +          break;
663 +        }
664 +
665 +      // Okay, it needs to be reused now
666 +      if (cur->type == PGBGP_REUSE_ORIGIN)
667 +        bgp_pgbgp_reuseOrigin (cur->data.origin);
668 +
669 +      else if (cur->type == PGBGP_REUSE_PREFIX)
670 +        bgp_pgbgp_reusePrefix (cur->data.prefix);
671 +
672 +      else if (cur->type == PGBGP_REUSE_EDGE)
673 +        bgp_pgbgp_reuseEdge (cur->data.edge);
674 +
675 +
676 +      XFREE (MTYPE_BGP_PGBGP_REUSE, cur);
677 +    }
678 +  return 0;
679 +}
680 +
681 +/* Check bit of the prefix. */
682 +static int
683 +check_bit (u_char * prefix, u_char prefixlen)
684 +{
685 +  int offset;
686 +  int shift;
687 +  u_char *p = (u_char *) prefix;
688 +
689 +  assert (prefixlen <= 128);
690 +
691 +  offset = prefixlen / 8;
692 +  shift = 7 - (prefixlen % 8);
693 +
694 +  return (p[offset] >> shift & 1);
695 +}
696 +
697 +/*
698 +  Find a super-net in the tree that's not currently anomalous if one exists
699 +*/
700 +struct bgp_node *
701 +findSuper (struct bgp_table *table, struct prefix *p, time_t t_now)
702 +{
703 +  struct bgp_node *node;
704 +  struct bgp_node *matched;
705 +
706 +  matched = NULL;
707 +  node = table->top;
708 +
709 +  while (node && node->p.prefixlen < p->prefixlen &&
710 +         prefix_match (&node->p, p))
711 +    {
712 +      // Node may not yet have its info set when reading in from pgbgp log files
713 +      if (node->hist && node->p.prefixlen >= 8)
714 +        {
715 +          if (node->hist->p != NULL && node->hist->p->ignoreUntil < t_now)
716 +            //if (node->hist->p != NULL && prefixInRIB (node, NULL))
717 +            //if (node->hist->p != NULL)
718 +            matched = node;
719 +        }
720 +      node = node->link[check_bit (&p->u.prefix, node->p.prefixlen)];
721 +    }
722 +  if (matched)
723 +    return bgp_lock_node (matched);
724 +  return NULL;
725 +}
726 +
727 +
728 +
729 +
730 +
731 +/*! --------------- Helper Functions ------------------ !*/
732 +
733 +
734 +
735 +
736 +
737 +
738 +
739 +/* --------------- Public PGBGP Interface ------------------ */
740 +int
741 +bgp_pgbgp_enable (struct bgp *bgp, afi_t afi, safi_t safi,
742 +                  int ost, int est, int sst, int oht, int pht, int eht,
743 +                  const char *file, const char *anoms)
744 +{
745 +
746 +  if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
747 +    {
748 +      if (pgbgp->storage && pgbgp->anomalies)
749 +        {
750 +          if (pgbgp->origin_sus_time == ost
751 +              && pgbgp->edge_sus_time == est
752 +              && pgbgp->sub_sus_time == sst
753 +              && pgbgp->origin_hist_time == oht
754 +              && pgbgp->prefix_hist_time == pht
755 +              && pgbgp->edge_hist_time == eht
756 +              && strcmp (pgbgp->storage, file) == 0
757 +              && strcmp (pgbgp->anomalies, anoms) == 0)
758 +
759 +            return 0;
760 +        }
761 +    }
762 +
763 +  SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP);
764 +
765 +#ifndef PGBGP_DEBUG
766 +  time_t hour = 3600;
767 +  time_t day = 86400;
768 +#endif
769 +#ifdef PGBGP_DEBUG
770 +  time_t hour = 2;
771 +  time_t day = 5;
772 +#endif
773 +
774 +  pgbgp->origin_sus_time = ost * hour;
775 +  pgbgp->edge_sus_time = est * hour;
776 +  pgbgp->sub_sus_time = sst * hour;
777 +  pgbgp->origin_hist_time = oht * day;
778 +  pgbgp->prefix_hist_time = pht * day;
779 +  pgbgp->edge_hist_time = eht * day;
780 +  pgbgp->peer_hist_time = DEFAULT_ORIGIN_HIST;
781 +
782 +  if (file != NULL)
783 +    pgbgp->storage = strdup (file);
784 +  else
785 +    pgbgp->storage = NULL;
786 +
787 +  if (anoms != NULL)
788 +    pgbgp->anomalies = strdup (anoms);
789 +  else
790 +    pgbgp->anomalies = NULL;
791 +
792 +
793 +  pgbgp->reuse_q = pqueue_create ();
794 +  pgbgp->reuse_q->cmp = reuse_cmp;
795 +  pgbgp->rq_size = 0;
796 +  pgbgp->lastgc = time (NULL);
797 +  pgbgp->lastStore = time (NULL);
798 +  pgbgp->startTime = time (NULL);
799 +  install_element (VIEW_NODE, &show_ip_bgp_pgbgp_cmd);
800 +  install_element (ENABLE_NODE, &show_ip_bgp_pgbgp_cmd);
801 +  install_element (VIEW_NODE, &show_ip_bgp_pgbgp_neighbors_cmd);
802 +  install_element (ENABLE_NODE, &show_ip_bgp_pgbgp_neighbors_cmd);
803 +  install_element (VIEW_NODE, &show_ip_bgp_pgbgp_origins_cmd);
804 +  install_element (ENABLE_NODE, &show_ip_bgp_pgbgp_origins_cmd);
805 +  pgbgp->edgeT = hash_create_size (131072, edge_key_make, edge_cmp);
806 +  bgp_pgbgp_restore ();
807 +  return 0;
808 +}
809 +
810 +int
811 +bgp_pgbgp_disable (struct bgp *bgp, afi_t afi, safi_t safi)
812 +{
813 +  UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP);
814 +
815 +  // Clean the tables
816 +  if (bgp->rib[afi][safi] != NULL)
817 +    bgp_pgbgp_clean (bgp->rib[afi][safi]);
818 +
819 +  bgp_pgbgp_cleanEdges ();
820 +
821 +  if (pgbgp->storage != NULL)
822 +    free (pgbgp->storage);
823 +
824 +  if (pgbgp->anomalies != NULL)
825 +    free (pgbgp->anomalies);
826 +
827 +  struct bgp_pgbgp_peerTime *pr = pgbgp->peerLast;
828 +  while (pr)
829 +    {
830 +      struct bgp_pgbgp_peerTime *cur = pr;
831 +      pr = pr->next;
832 +      XFREE (MTYPE_BGP_PGBGP_PEER, cur);
833 +    }
834 +
835 +  return 0;
836 +}
837 +
838 +int
839 +bgp_pgbgp_clean (struct bgp_table *table)
840 +{
841 +  struct bgp_pgbgp_reuse *rnode = NULL;
842 +
843 +  while (pgbgp->rq_size > 0)
844 +    {
845 +      rnode = (struct bgp_pgbgp_reuse *) pqueue_dequeue (pgbgp->reuse_q);
846 +      pgbgp->rq_size -= 1;
847 +      XFREE (MTYPE_BGP_PGBGP_REUSE, rnode);
848 +    }
849 +  pqueue_delete (pgbgp->reuse_q);
850 +
851 +  if (table == NULL)
852 +    return 0;
853 +
854 +  // Clean the detectors
855 +  bgp_pgbgp_cleanHistTable (table);
856 +
857 +  bgp_pgbgp_cleanEdges ();
858 +
859 +
860 +  // Clean up the RIB nodes
861 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
862 +       rn = bgp_route_next (rn))
863 +    {
864 +      int changed = 0;
865 +      for (struct bgp_info * ri = rn->info; ri; ri = ri->next)
866 +        {
867 +          if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O
868 +                          | BGP_INFO_SUSPICIOUS_P | BGP_INFO_SUSPICIOUS_E
869 +                          | BGP_INFO_IGNORED_P))
870 +            {
871 +              changed = 1;
872 +              UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O
873 +                          | BGP_INFO_SUSPICIOUS_P | BGP_INFO_SUSPICIOUS_E
874 +                          | BGP_INFO_IGNORED_P);
875 +            }
876 +        }
877 +      if (changed && rn->info)
878 +        {
879 +          struct bgp_info *ri = rn->info;
880 +          bgp_process (ri->peer->bgp, rn, rn->table->afi, rn->table->safi);
881 +        }
882 +    }
883 +
884 +  hash_free (pgbgp->edgeT);
885 +  return 0;
886 +}
887 +
888 +
889 +int
890 +bgp_pgbgp_gc (struct bgp_table *table)
891 +{
892 +  struct bgp *bgp = bgp_get_default ();
893 +  if (!bgp)
894 +    return 0;
895 +
896 +  // Collect each AFI/SAFI RIB
897 +  for (afi_t afi = AFI_IP; afi < AFI_MAX; afi++)
898 +    for (safi_t safi = SAFI_UNICAST; safi < SAFI_MAX; safi++)
899 +      {
900 +        if (!CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
901 +          continue;
902 +        struct bgp_table *curTable = bgp->rib[afi][safi];
903 +        if (!curTable)
904 +          continue;
905 +        bgp_pgbgp_garbageCollectHistTable (curTable);
906 +      }
907 +
908 +  bgp_pgbgp_garbageCollectEdges (table);
909 +
910 +  return 0;
911 +}
912 +
913 +int
914 +bgp_pgbgp_restore (void)
915 +{
916 +
917 +  if (pgbgp->storage == NULL)
918 +    return 0;
919 +  FILE *file = fopen (pgbgp->storage, "r");
920 +  if (!file)
921 +    return 0;
922 +
923 +  int type = 0;
924 +  struct prefix p;
925 +  struct bgp *bgp = bgp_get_default ();
926 +  struct bgp_node *curNode = NULL;
927 +
928 +  // Get the log store time
929 +  long long int writetime;
930 +  fscanf (file, "%lld", &writetime);
931 +  time_t swtime = writetime;
932 +
933 +  // If it's too old (more than 1 week old), start fresh
934 +  if (time (NULL) - swtime > 86400 * 7)
935 +    {
936 +      fclose (file);
937 +      return 0;
938 +    }
939 +
940 +
941 +  // Get the PGBGP init time
942 +  long long int stime;
943 +  fscanf (file, "%lld", &stime);
944 +  pgbgp->startTime = stime;
945 +
946 +  while (fscanf (file, "%d", &type) != EOF)
947 +    {
948 +
949 +      if (type == PREFIX_ID)
950 +        {
951 +          char pre[128];
952 +          unsigned int afi;
953 +          unsigned int safi;
954 +          long long int time;
955 +          fscanf (file, "%s %u %u %lld", pre, &afi, &safi, &time);
956 +          str2prefix (pre, &p);
957 +          struct bgp_table *curTable = bgp->rib[afi][safi];
958 +          assert (curTable != NULL);
959 +
960 +          // Create and lock the node
961 +          curNode = bgp_node_get (curTable, &p);
962 +          assert (curNode->hist == NULL);
963 +
964 +          //              bgp_lock_node(curNode);
965 +
966 +          curNode->hist =
967 +            XCALLOC (MTYPE_BGP_PGBGP_HIST, sizeof (struct bgp_pgbgp_hist));
968 +          assert (curNode->hist != NULL);
969 +
970 +          curNode->hist->p =
971 +            XCALLOC (MTYPE_BGP_PGBGP_PREFIX,
972 +                     sizeof (struct bgp_pgbgp_prefix));
973 +          assert (curNode->hist->p != NULL);
974 +
975 +          curNode->hist->p->lastSeen = time;
976 +        }
977 +      else if (type == ORIGIN_ID)
978 +        {
979 +          unsigned int ASN;
980 +          long long int time;
981 +          fscanf (file, "%u %lld", &ASN, &time);
982 +          struct bgp_pgbgp_origin *or = XCALLOC (MTYPE_BGP_PGBGP_ORIGIN,
983 +                                                 sizeof (struct
984 +                                                         bgp_pgbgp_origin));
985 +          or->lastSeen = time;
986 +          or->originAS = ASN;
987 +          or->next = curNode->hist->o;
988 +          curNode->hist->o = or;
989 +        }
990 +      else if (type == EDGE_ID)
991 +        {
992 +          bgp_pgbgp_restoreEdge (file);
993 +        }
994 +      else if (type == PEER_ID)
995 +        {
996 +          struct bgp_pgbgp_peerTime *pr;
997 +          long long int time;
998 +          union sockunion su;
999 +          char szsu[128];
1000 +          fscanf (file, "%s %lld", szsu, &time);
1001 +          str2sockunion (szsu, &su);
1002 +          pr =
1003 +            XCALLOC (MTYPE_BGP_PGBGP_PEER,
1004 +                     sizeof (struct bgp_pgbgp_peerTime));
1005 +          pr->su = su;
1006 +          pr->lastSeen = time;
1007 +          pr->next = pgbgp->peerLast;
1008 +          pgbgp->peerLast = pr;
1009 +        }
1010 +    }
1011 +
1012 +  fclose (file);
1013 +  return 0;
1014 +}
1015 +
1016 +int
1017 +bgp_pgbgp_store (struct bgp_table *table)
1018 +{
1019 +  if (pgbgp->storage == NULL)
1020 +    return 0;
1021 +  char *tmpname = malloc (sizeof (char) * (1 + 4 + strlen (pgbgp->storage)));
1022 +  strcpy (tmpname, pgbgp->storage);
1023 +  strcat (tmpname, ".tmp");
1024 +  FILE *file = fopen (tmpname, "w");
1025 +
1026 +  if (!file)
1027 +    {
1028 +      free (tmpname);
1029 +      return 0;
1030 +    }
1031 +
1032 +  // Store the current time
1033 +  fprintf (file, "%lld\n", (long long int) time (NULL));
1034 +
1035 +  // Store the init time
1036 +  fprintf (file, "%lld\n", (long long int) pgbgp->startTime);
1037 +
1038 +  // Store the peer times
1039 +  for (struct bgp_pgbgp_peerTime * pr = pgbgp->peerLast; pr; pr = pr->next)
1040 +    {
1041 +      char strSock[128];
1042 +      sockunion2str (&pr->su, strSock, sizeof (strSock));
1043 +
1044 +      if (pr->deprefUntil < time (NULL))
1045 +        {
1046 +          fprintf (file, "%d %s %lld\n", PEER_ID, strSock,
1047 +                   (long long int) pr->lastSeen);
1048 +        }
1049 +    }
1050 +
1051 +  // Store the tables
1052 +  bgp_pgbgp_storeHistTable (table, file);
1053 +  bgp_pgbgp_storeEdges (table, file);
1054 +
1055 +  fclose (file);
1056 +
1057 +  rename (tmpname, pgbgp->storage);
1058 +
1059 +  free (tmpname);
1060 +  return 0;
1061 +}
1062 +
1063 +/*
1064 +  Check to see if we've seen the peer recently
1065 +  If not, then we need to return true and not delay routes
1066 +  for awhile
1067 +*/
1068 +int
1069 +bgp_pgbgp_updatePeer (struct bgp_info *binfo, time_t now)
1070 +{
1071 +  int status = false;
1072 +  // Find the peer
1073 +  struct bgp_pgbgp_peerTime *pr = pgbgp->peerLast;
1074 +  for (; pr; pr = pr->next)
1075 +    if (sockunion_same (&pr->su, &binfo->peer->su))
1076 +      break;
1077 +
1078 +  // If this is a new peer, create it
1079 +  if (pr == NULL)
1080 +    {
1081 +      pr = XCALLOC (MTYPE_BGP_PGBGP_PEER, sizeof (struct bgp_pgbgp_peerTime));
1082 +      pr->su = binfo->peer->su;
1083 +      pr->next = pgbgp->peerLast;
1084 +      pgbgp->peerLast = pr;
1085 +
1086 +    }
1087 +  // Is it currently marked as new?
1088 +  if (pr->deprefUntil > now)
1089 +    goto UPPEER_DEPREF;
1090 +
1091 +  // Have we seen the peer recently?
1092 +  if (pr->lastSeen + pgbgp->peer_hist_time > now)
1093 +    goto UPPEER_CLEAN;
1094 +
1095 +  // It must not have been seen lately, depref it
1096 +  pr->deprefUntil = now + PGBGP_PEER_GRACE;
1097 +
1098 +
1099 +UPPEER_DEPREF:
1100 +  status = true;
1101 +
1102 +UPPEER_CLEAN:
1103 +  pr->lastSeen = now;
1104 +
1105 +  return status;
1106 +}
1107 +
1108 +
1109 +/*
1110 +  Returns whether or not the sub-prefix should be ignored
1111 +*/
1112 +int
1113 +bgp_pgbgp_shouldIgnore (struct bgp_node *super, struct bgp_info *selected)
1114 +{
1115 +  if (!selected || CHECK_FLAG (selected->flags, BGP_INFO_SUSPICIOUS_P))
1116 +    return false;
1117 +  return true;
1118 +}
1119 +
1120 +/*
1121 +  This is a special case function for smoothly handling sub-prefix hijacks.
1122 +
1123 +  It handles the following 2 events:
1124 +
1125 +  Event 1: The super-prefix of an anomalous prefix has a route through a non-anomalous
1126 +
1127 +  Event 1: An anomalous sub-prefix is ignored, but no best route for the super-prefix exists
1128 +  Response: Announce the sub-prefix until the super-prefix comes back
1129 +
1130 +  Event 2: A super-prefix comes back to the RIB and its anomalous sub-prefix is in use
1131 +  Response: Ignore the sub-prefix again
1132 + */
1133 +
1134 +
1135 +int
1136 +bgp_pgbgp_rib_updated (struct bgp_node *rn, struct bgp_info *old_best,
1137 +                       struct bgp_info *new_best)
1138 +{
1139 +  //  return 0;
1140 +  struct bgp_pgbgp_hist *hist = rn->hist;
1141 +  if (!hist)
1142 +    return 0;
1143 +  if (!hist->p)
1144 +    return 0;
1145 +  time_t t_now = time (NULL);
1146 +
1147 +  /*
1148 +     If we can't avoid the sub-prefix by routing to the super-prefix,
1149 +     then route as normal to the sub-prefix
1150 +   */
1151 +  if (!bgp_pgbgp_shouldIgnore (rn, new_best))
1152 +    {
1153 +      for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1154 +           cur = cur->next)
1155 +        {
1156 +          if (cur->avoidUntil > t_now)
1157 +            {
1158 +              int changed = false;
1159 +              for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1160 +                {
1161 +                  if (CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
1162 +                    {
1163 +                      changed = true;
1164 +                      UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1165 +                    }
1166 +                }
1167 +              if (changed)
1168 +                {
1169 +                  struct bgp_info *ri = cur->sub->info;
1170 +                  if (ri && ri->peer && ri->peer->bgp)
1171 +                    bgp_process (ri->peer->bgp, cur->sub,
1172 +                                 cur->sub->table->afi, cur->sub->table->safi);
1173 +
1174 +                }
1175 +
1176 +            }
1177 +        }
1178 +    }
1179 +
1180 +  /* 
1181 +     If we can avoid the sub-prefix by routing to the super-prefix,
1182 +     then do so
1183 +   */
1184 +
1185 +  else
1186 +    {
1187 +      for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1188 +           cur = cur->next)
1189 +        {
1190 +          if (cur->avoidUntil > t_now)
1191 +            {
1192 +              int changed = false;
1193 +              for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1194 +                {
1195 +                  if (!CHECK_FLAG (ri->flags, BGP_INFO_IGNORED_P))
1196 +                    {
1197 +                      changed = true;
1198 +                      SET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1199 +                    }
1200 +                }
1201 +              if (changed)
1202 +                {
1203 +                  struct bgp_info *ri = cur->sub->info;
1204 +                  if (ri && ri->peer && ri->peer->bgp)
1205 +                    bgp_process (ri->peer->bgp, cur->sub,
1206 +                                 cur->sub->table->afi, cur->sub->table->safi);
1207 +                }
1208 +            }
1209 +        }
1210 +    }
1211 +
1212 +  /*
1213 +     if (old_best && !new_best)
1214 +     {
1215 +     time_t t_now = time(NULL);
1216 +     for (struct bgp_pgbgp_avoid * cur = hist->p->avoid; cur;
1217 +     cur = cur->next)
1218 +     {
1219 +     if (cur->avoidUntil > t_now)
1220 +     {
1221 +     for (struct bgp_info * ri = cur->sub->info; ri; ri = ri->next)
1222 +     UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1223 +
1224 +     struct bgp_info *ri = cur->sub->info;
1225 +     if (ri && ri->peer && ri->peer->bgp)
1226 +     bgp_process (ri->peer->bgp, cur->sub, cur->sub->table->afi,
1227 +     cur->sub->table->safi);
1228 +     }
1229 +     }      
1230 +     }
1231 +
1232 +
1233 +     else if (!old_best && new_best)
1234 +     {
1235 +     time_t t_now = time(NULL);
1236 +     for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av; av = av->next)
1237 +     {
1238 +     struct bgp_info * ri = av->sub->info;
1239 +     if (av->avoidUntil > t_now && ri && !CHECK_FLAG(ri->flags, BGP_INFO_IGNORED_P)) 
1240 +     {
1241 +     for (; ri; ri = ri->next)
1242 +     SET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1243 +     ri = av->sub->info;
1244 +     if (ri && ri->peer && ri->peer->bgp)
1245 +     bgp_process (ri->peer->bgp, av->sub,
1246 +     av->sub->table->afi, av->sub->table->safi);
1247 +
1248 +     }
1249 +     }      
1250 +     }
1251 +   */
1252 +  return 0;
1253 +}
1254 +
1255 +int
1256 +bgp_pgbgp_update (struct bgp_info *binfo, struct attr *at,
1257 +                  struct bgp_node *rn)
1258 +{
1259 +  time_t t_now = time (NULL);
1260 +
1261 +  // Clean up the reuse list
1262 +  bgp_pgbgp_reuse (t_now);
1263 +
1264 +
1265 +  if (!rn->hist)
1266 +    {
1267 +      rn->hist =
1268 +        XCALLOC (MTYPE_BGP_PGBGP_HIST, sizeof (struct bgp_pgbgp_hist));
1269 +      // Get the PGBGP history lock on rn
1270 +      bgp_lock_node (rn);
1271 +    }
1272 +
1273 +  struct bgp_node *superhn = NULL;
1274 +
1275 +  // implicit lock from node_get
1276 +  superhn = findSuper (rn->table, &rn->p, t_now);
1277 +
1278 +  int newPeer = bgp_pgbgp_updatePeer (binfo, t_now);
1279 +  bgp_pgbgp_updateOrigin (rn->hist, binfo, at, rn, t_now, newPeer);
1280 +  bgp_pgbgp_updatePrefix (rn->hist, superhn, binfo, at, rn, t_now, newPeer);
1281 +  bgp_pgbgp_updateEdge (rn->hist, binfo, at, rn, t_now, newPeer);
1282 +
1283 +  if (superhn != NULL)
1284 +    bgp_unlock_node (superhn);
1285 +
1286 +
1287 +
1288 +  // GC and storage must be last, as they update lastSeen values of objects
1289 +  // which would cause new routes to be recently seen, which is undesired behavior
1290 +  // Make sure you don't collect anything that might be in use!
1291 +  if (t_now >= pgbgp->lastgc + PGBGP_GC_DELTA)
1292 +    {
1293 +      bgp_pgbgp_gc (rn->table);
1294 +      pgbgp->lastgc = t_now;
1295 +    }
1296 +
1297 +  if (t_now >= pgbgp->lastStore + PGBGP_STORE_DELTA)
1298 +    {
1299 +      bgp_pgbgp_store (rn->table);
1300 +      pgbgp->lastStore = t_now;
1301 +    }
1302 +
1303 +
1304 +
1305 +  return 0;
1306 +}
1307 +
1308 +
1309 +
1310 +
1311 +/*! --------------- Public PGBGP Interface ------------------ !*/
1312 +
1313 +
1314 +
1315 +
1316 +
1317 +
1318 +
1319 +
1320 +
1321 +/* --------------- MOAS Detection ------------------ */
1322 +void
1323 +bgp_pgbgp_storeHistTable (struct bgp_table *table, FILE * file)
1324 +{
1325 +  time_t t_now;
1326 +  t_now = time (NULL);
1327 +
1328 +  struct bgp *bgp = bgp_get_default ();
1329 +  if (!bgp)
1330 +    return;
1331 +
1332 +  // Store each AFI/SAFI RIB
1333 +  for (afi_t afi = AFI_IP; afi < AFI_MAX; afi++)
1334 +    for (safi_t safi = SAFI_UNICAST; safi < SAFI_MAX; safi++)
1335 +      {
1336 +        if (!CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_PGBGP))
1337 +          continue;
1338 +        struct bgp_table *curTable = bgp->rib[afi][safi];
1339 +        if (!curTable)
1340 +          continue;
1341 +
1342 +        for (struct bgp_node * rn = bgp_table_top (curTable); rn;
1343 +             rn = bgp_route_next (rn))
1344 +          {
1345 +            struct bgp_pgbgp_hist *hist = rn->hist;
1346 +            if (hist == NULL)
1347 +              continue;
1348 +            char szPrefix[128];
1349 +            prefix2str (&rn->p, szPrefix, sizeof (szPrefix));
1350 +
1351 +
1352 +            struct bgp_pgbgp_prefix *pre = hist->p;
1353 +            if (pre && pre->ignoreUntil <= t_now)
1354 +              {
1355 +                if (pre->lastSeen + pgbgp->prefix_hist_time > t_now)
1356 +                  fprintf (file, "%d %s %u %u %lld\n", PREFIX_ID, szPrefix,
1357 +                           (unsigned int) afi, (unsigned int) safi,
1358 +                           (long long int) pre->lastSeen);
1359 +                else
1360 +                  continue;
1361 +              }
1362 +            /* Need a prefix in the file before the origins, 
1363 +               if no prefix.. skip origins */
1364 +            else
1365 +              continue;
1366 +
1367 +            for (struct bgp_pgbgp_origin * cur = hist->o; cur;
1368 +                 cur = cur->next)
1369 +              {
1370 +                if (cur->deprefUntil > t_now)
1371 +                  continue;
1372 +
1373 +                if (cur->lastSeen + pgbgp->origin_hist_time > t_now)
1374 +                  fprintf (file, "%d %u %lld\n", ORIGIN_ID, cur->originAS,
1375 +                           (long long int) cur->lastSeen);
1376 +              }
1377 +
1378 +          }
1379 +      }
1380 +}
1381 +
1382 +
1383 +int
1384 +bgp_pgbgp_garbageCollectHistTable (struct bgp_table *table)
1385 +{
1386 +  time_t t_now;
1387 +  t_now = time (NULL);
1388 +
1389 +
1390 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
1391 +       rn = bgp_route_next (rn))
1392 +    {
1393 +      int collect = false;
1394 +      struct bgp_pgbgp_hist *hist = rn->hist;
1395 +      if (hist == NULL)
1396 +        continue;
1397 +
1398 +      struct bgp_pgbgp_origin *cur = hist->o;
1399 +      struct bgp_pgbgp_prefix *pre = hist->p;
1400 +      struct bgp_pgbgp_origin *parent = NULL;
1401 +
1402 +      int used = false;
1403 +      if (cur != NULL || pre != NULL)
1404 +        used = true;
1405 +
1406 +      while (cur != NULL)
1407 +        {
1408 +          // Update the lastSeen time w/ originInRIB
1409 +          if (originInRIB (rn, cur))
1410 +            cur->lastSeen = t_now;
1411 +
1412 +          collect = false;
1413 +
1414 +          // Collect if old
1415 +          if (cur->lastSeen + pgbgp->origin_hist_time <= t_now)
1416 +            collect = true;
1417 +
1418 +          // Collect if anomaly just became okay but not seen since last collection
1419 +          if (cur->deprefUntil != 0 && cur->deprefUntil < t_now)
1420 +            {
1421 +              if (cur->lastSeen < pgbgp->lastgc)
1422 +                collect = true;
1423 +              cur->deprefUntil = 0;
1424 +            }
1425 +
1426 +          if (collect)
1427 +            {
1428 +              if (parent == NULL)
1429 +                hist->o = cur->next;
1430 +              else
1431 +                parent->next = cur->next;
1432 +
1433 +              // Delete cur, parent doesn't change
1434 +              struct bgp_pgbgp_origin *del = cur;
1435 +              cur = cur->next;
1436 +              XFREE (MTYPE_BGP_PGBGP_ORIGIN, del);
1437 +            }
1438 +          else
1439 +            {
1440 +              parent = cur;
1441 +              cur = cur->next;
1442 +            }
1443 +        }
1444 +
1445 +      // Update the lastSeen time w/ prefixInRIB
1446 +      if (pre && prefixInRIB (rn, pre))
1447 +        pre->lastSeen = t_now;
1448 +
1449 +      collect = false;
1450 +
1451 +      // Collect if old
1452 +      if (pre && pre->lastSeen + pgbgp->prefix_hist_time <= t_now)
1453 +        collect = true;
1454 +
1455 +      // Collect if anomaly just became okay but not seen since last collection
1456 +      if (pre && pre->ignoreUntil != 0 && pre->ignoreUntil < t_now)
1457 +        {
1458 +          if (pre->lastSeen < pgbgp->lastgc)
1459 +            collect = true;
1460 +          pre->ignoreUntil = 0;
1461 +        }
1462 +
1463 +      if (collect)
1464 +        {
1465 +          for (struct bgp_pgbgp_avoid * av = pre->avoid; av;)
1466 +            {
1467 +              struct bgp_pgbgp_avoid *del = av;
1468 +              av = av->next;
1469 +              bgp_unlock_node (del->sub);
1470 +              XFREE (MTYPE_BGP_PGBGP_AVOID, del);
1471 +            }
1472 +
1473 +          XFREE (MTYPE_BGP_PGBGP_PREFIX, pre);
1474 +          hist->p = NULL;
1475 +        }
1476 +
1477 +      // If the node isn't in use, remove it
1478 +      if (used && hist->o == NULL && hist->p == NULL)
1479 +        {
1480 +          XFREE (MTYPE_BGP_PGBGP_HIST, hist);
1481 +          rn->hist = NULL;
1482 +          bgp_unlock_node (rn);
1483 +        }
1484 +    }
1485 +
1486 +  return 0;
1487 +}
1488 +
1489 +void
1490 +bgp_pgbgp_cleanHistTable (struct bgp_table *table)
1491 +{
1492 +  // Clean up the RIB nodes
1493 +  for (struct bgp_node * rn = bgp_table_top (table); rn;
1494 +       rn = bgp_route_next (rn))
1495 +    {
1496 +      struct bgp_pgbgp_hist *hist = rn->hist;
1497 +      if (hist == NULL)
1498 +        continue;
1499 +
1500 +      if (hist->p)
1501 +        {
1502 +          for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av;)
1503 +            {
1504 +              struct bgp_pgbgp_avoid *del = av;
1505 +              av = av->next;
1506 +              bgp_unlock_node (del->sub);
1507 +              XFREE (MTYPE_BGP_PGBGP_AVOID, del);
1508 +            }
1509 +          hist->p->avoid = NULL;
1510 +          XFREE (MTYPE_BGP_PGBGP_PREFIX, hist->p);
1511 +          hist->p = NULL;
1512 +        }
1513 +
1514 +      for (struct bgp_pgbgp_origin * cur = hist->o; cur;)
1515 +        {
1516 +          struct bgp_pgbgp_origin *next = cur->next;
1517 +          XFREE (MTYPE_BGP_PGBGP_ORIGIN, cur);
1518 +          cur = next;
1519 +        }
1520 +      hist->o = NULL;
1521 +      XFREE (MTYPE_BGP_PGBGP_HIST, hist);
1522 +      rn->hist = NULL;
1523 +      bgp_unlock_node (rn);
1524 +    }
1525 +}
1526 +
1527 +void
1528 +bgp_pgbgp_logOriginAnomaly (as_t asn, struct bgp_node *rn, struct attr *at)
1529 +{
1530 +  assert (pgbgp);
1531 +  if (!pgbgp->anomalies)
1532 +    return;
1533 +  FILE *file = fopen (pgbgp->anomalies, "a");
1534 +  if (!file)
1535 +    return;
1536 +
1537 +  char pre[256];
1538 +  prefix2str (&rn->p, pre, sizeof (pre));
1539 +
1540 +  // MOAS | TIME | NEXTHOP | PREFIX | SUSPICIOUS_ORIGIN | TRUSTED_ORIGINS | PATH
1541 +  fprintf (file, "%d|%lld|%s|%s|%d|", MOAS, (long long int) time (NULL),
1542 +           inet_ntoa (at->nexthop), pre, asn);
1543 +
1544 +
1545 +  // Print the trusted origins
1546 +  assert (rn->hist);
1547 +  assert (rn->hist->o);
1548 +
1549 +  struct bgp_pgbgp_hist *hist = rn->hist;
1550 +
1551 +  for (struct bgp_pgbgp_origin * cur = hist->o; cur != NULL; cur = cur->next)
1552 +    {
1553 +      if (cur->deprefUntil > time (NULL))
1554 +        continue;
1555 +      fprintf (file, "%d", cur->originAS);
1556 +      if (cur->next != NULL)
1557 +        fprintf (file, " ");
1558 +    }
1559 +
1560 +  fprintf (file, " |%s\n", aspath_print (at->aspath));
1561 +  fclose (file);
1562 +}
1563 +
1564 +int
1565 +bgp_pgbgp_updateOrigin (struct bgp_pgbgp_hist *hist, struct bgp_info *binfo,
1566 +                        struct attr *at, struct bgp_node *rn, time_t t_now,
1567 +                        int newPeer)
1568 +{
1569 +  struct bgp_pgbgp_pathSet pathOrigins;
1570 +  struct bgp_pgbgp_origin *pi = NULL;
1571 +  int status = 0;
1572 +  struct bgp_pgbgp_reuse *r;
1573 +  pathOrigins = bgp_pgbgp_pathOrigin (at->aspath);
1574 +
1575 +
1576 +  for (int i = 0; i < pathOrigins.length; i++)
1577 +    {
1578 +      as_t pathOrigin = pathOrigins.ases[i];
1579 +
1580 +      /* Is the Origin AS in the history? */
1581 +      for (pi = hist->o; pi; pi = pi->next)
1582 +        if (pi->originAS == pathOrigin)
1583 +          break;
1584 +
1585 +      if (pi == NULL)
1586 +        {
1587 +          pi =
1588 +            XCALLOC (MTYPE_BGP_PGBGP_ORIGIN,
1589 +                     sizeof (struct bgp_pgbgp_origin));
1590 +          pi->next = hist->o;
1591 +          pi->originAS = pathOrigin;
1592 +          hist->o = pi;
1593 +        }
1594 +
1595 +      // If this is our first origin for the prefix, let the sub-prefix
1596 +      // check take care of it
1597 +      if (pi->next == NULL)
1598 +        goto UPO_CLEAN;
1599 +
1600 +      /* Is the origin currently marked as suspicious? */
1601 +      if (pi->deprefUntil > t_now)
1602 +        goto UPO_DEPREF;
1603 +
1604 +      /* Have we seen the origin recently? */
1605 +      if (pi->lastSeen + pgbgp->origin_hist_time > t_now)
1606 +        goto UPO_CLEAN;
1607 +
1608 +#ifndef PGBGP_DEBUG
1609 +      /* Are we within the initial grace period? */
1610 +      if (newPeer)
1611 +        goto UPO_CLEAN;
1612 +#endif
1613 +
1614 +      /* It must not be in recent history, depref origin for first time */
1615 +      pi->deprefUntil = t_now + pgbgp->origin_sus_time;
1616 +      bgp_pgbgp_logOriginAnomaly (pathOrigin, rn, at);
1617 +
1618 +      r = XCALLOC (MTYPE_BGP_PGBGP_REUSE, sizeof (struct bgp_pgbgp_reuse));
1619 +      r->type = PGBGP_REUSE_ORIGIN;
1620 +      r->deprefUntil = pi->deprefUntil;
1621 +      r->data.origin.originAS = pathOrigin;
1622 +      r->data.origin.rn = rn;
1623 +      bgp_lock_node (rn);
1624 +      pqueue_enqueue (r, pgbgp->reuse_q);
1625 +      pgbgp->rq_size += 1;
1626 +
1627 +
1628 +    UPO_DEPREF:
1629 +      SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_O);
1630 +      status = BGP_INFO_SUSPICIOUS_O;
1631 +
1632 +    UPO_CLEAN:
1633 +      pi->lastSeen = t_now;
1634 +    }
1635 +  return status;
1636 +}
1637 +
1638 +int
1639 +bgp_pgbgp_reuseOrigin (struct bgp_pgbgp_r_origin data)
1640 +{
1641 +  struct bgp_info *ri;
1642 +  int numChanged = 0;
1643 +  time_t t_now = time (NULL);
1644 +  assert (data.rn->hist != NULL);
1645 +
1646 +  // Repreference paths for this prefix that are now okay
1647 +  for (ri = data.rn->info; ri; ri = ri->next)
1648 +    {
1649 +      if (CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O))
1650 +        {
1651 +          struct bgp_pgbgp_pathSet pathOrigins;
1652 +          pathOrigins = bgp_pgbgp_pathOrigin (ri->attr->aspath);
1653 +          int numOkay = 0;
1654 +          for (int i = 0; i < pathOrigins.length; i++)
1655 +            {
1656 +              as_t pathOrigin = pathOrigins.ases[i];
1657 +              // Find the origin
1658 +              struct bgp_pgbgp_origin *o = NULL;
1659 +              for (o = data.rn->hist->o; o != NULL; o = o->next)
1660 +                if (o->originAS == pathOrigin)
1661 +                  break;
1662 +              /*
1663 +                 if (o == NULL) {
1664 +                 for(struct bgp_pgbgp_origin * z = data.rn->hist->o; z != NULL; z = z->next)
1665 +                 printf("Known origin: %d\n", z->originAS);
1666 +                 char pre[128];
1667 +                 prefix2str(&data.rn->p, pre, 128);
1668 +                 printf("%s : %s : %d\n", pre, ri->attr->aspath->str, pathOrigin);
1669 +                 }
1670 +               */
1671 +              assert (o != NULL);
1672 +
1673 +              if (o->deprefUntil <= t_now)
1674 +                numOkay += 1;
1675 +            }
1676 +          if (numOkay == pathOrigins.length)
1677 +            {
1678 +              UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_O);
1679 +              numChanged += 1;
1680 +            }
1681 +        }
1682 +    }
1683 +
1684 +  ri = data.rn->info;
1685 +
1686 +  // Rerun the decision process?
1687 +  if (numChanged > 0)
1688 +    bgp_process (ri->peer->bgp, data.rn, data.rn->table->afi,
1689 +                 data.rn->table->safi);
1690 +
1691 +
1692 +  /*
1693 +     // Remove this (origin,prefix) pair from the normal database
1694 +     // if it's not still in the RIB
1695 +     struct bgp_pgbgp_hist *hist = rn->hist;
1696 +     struct bgp_pgbgp_origin * cur = hist->o;
1697 +     struct bgp_pgbgp_origin * parent = NULL;
1698 +
1699 +     // Find the origin AS node
1700 +     while(cur != NULL)
1701 +     {
1702 +     if (cur->originAS == data.originAS)
1703 +     {
1704 +     // Delete the node if it hasn't been seen
1705 +     // since the last storage run
1706 +     if (cur->lastSeen < pgbgp->lastStore) {
1707 +     // Delete this node
1708 +     if (parent == NULL)
1709 +     hist->o = cur->next;
1710 +     else
1711 +     parent->next = cur->next;
1712 +
1713 +     XFREE(MTYPE_BGP_PGBGP_ORIGIN, cur);
1714 +     }
1715 +     break;
1716 +     }      
1717 +     parent = cur;
1718 +     cur = cur->next;
1719 +     }
1720 +   */
1721 +
1722 +  bgp_unlock_node (data.rn);
1723 +  return 0;
1724 +}
1725 +
1726 +/*! --------------- MOAS Detection ------------------ !*/
1727 +
1728 +
1729 +/* --------------- Sub-Prefix Detection ------------------ */
1730 +
1731 +
1732 +
1733 +
1734 +
1735 +void
1736 +bgp_pgbgp_logSubprefixAnomaly (as_t asn, struct bgp_node *rn, struct attr *at,
1737 +                               struct bgp_node *super)
1738 +{
1739 +  assert (pgbgp);
1740 +  if (!pgbgp->anomalies)
1741 +    return;
1742 +  FILE *file = fopen (pgbgp->anomalies, "a");
1743 +  if (!file)
1744 +    return;
1745 +
1746 +  char pre[256];
1747 +  prefix2str (&rn->p, pre, sizeof (pre));
1748 +
1749 +  char superpre[256];
1750 +  prefix2str (&super->p, superpre, sizeof (superpre));
1751 +
1752 +  // SUBPREFIX | TIME | NEXTHOP | PREFIX | SUPER-PREFIX | SUSPICIOUS_ORIGIN | TRUSTED_ORIGINS | PATH
1753 +  fprintf (file, "%d|%lld|%s|%s|%s|%d|", SUBPREFIX,
1754 +           (long long int) time (NULL), inet_ntoa (at->nexthop), pre,
1755 +           superpre, asn);
1756 +
1757 +  // Print the trusted origins
1758 +  assert (super->hist);
1759 +  assert (super->hist->o);
1760 +
1761 +  struct bgp_pgbgp_hist *hist = super->hist;
1762 +
1763 +  for (struct bgp_pgbgp_origin * cur = hist->o; cur != NULL; cur = cur->next)
1764 +    {
1765 +      if (cur->deprefUntil > time (NULL))
1766 +        continue;
1767 +      fprintf (file, "%d", cur->originAS);
1768 +      if (cur->next != NULL)
1769 +        fprintf (file, " ");
1770 +    }
1771 +
1772 +  fprintf (file, " |%s\n", aspath_print (at->aspath));
1773 +  fclose (file);
1774 +}
1775 +
1776 +/*
1777 +  If the first path is a prefix of the second, then return true  
1778 + */
1779 +
1780 +static int
1781 +bgp_pgbgp_pathIsPrefix(struct aspath *trusted, struct aspath * new)
1782 +{
1783 +  if (trusted == new)
1784 +    return true;
1785 +  
1786 +  struct assegment *seg1 = trusted->segments;
1787 +  struct assegment *seg2 = new->segments;
1788 +  
1789 +  while (seg1 || seg2)
1790 +    {
1791 +      if ((!seg1 && seg2) || (seg1 && !seg2))
1792 +       return false;
1793 +      if (seg1->type != seg2->type)
1794 +       return false;
1795 +      
1796 +      if (seg1->length > seg2->length)
1797 +       return false;
1798 +         
1799 +      for(int i = 0; i < seg1->length; i++)
1800 +       if (seg1->as[i] != seg2->as[i])
1801 +         return false;
1802 +
1803 +      seg1 = seg1->next;
1804 +      seg2 = seg2->next;
1805 +    }  
1806 +
1807 +  return true;
1808 +}
1809 +
1810 +int
1811 +bgp_pgbgp_updatePrefix (struct bgp_pgbgp_hist *hist,
1812 +                        struct bgp_node *supernode, struct bgp_info *binfo,
1813 +                        struct attr *at, struct bgp_node *rn, time_t t_now,
1814 +                        int newPeer)
1815 +{
1816 +  struct bgp_pgbgp_prefix *pre = NULL;
1817 +  struct bgp_pgbgp_reuse *r = NULL;
1818 +  int status = 0;
1819 +  int changed = false;
1820 +
1821 +  pre = hist->p;
1822 +
1823 +
1824 +  /* Do we have this prefix? */
1825 +  if (pre == NULL)
1826 +    {
1827 +      pre =
1828 +        XCALLOC (MTYPE_BGP_PGBGP_PREFIX, sizeof (struct bgp_pgbgp_prefix));
1829 +      hist->p = pre;
1830 +    }
1831 +
1832 +  /* Is the prefix currently marked as suspicious? */
1833 +  if (pre->ignoreUntil > t_now)
1834 +    {
1835 +      goto UPP_IGNORE;
1836 +    }
1837 +
1838 +  /* Should this neighbor be avoided for this prefix because it
1839 +     sent us info. about a suspicious sub-prefix? */
1840 +  for (struct bgp_pgbgp_avoid * av = hist->p->avoid; av; av = av->next)
1841 +    {
1842 +      if (binfo->peer->as == av->peerASN && av->avoidUntil > t_now)
1843 +        {
1844 +          SET_FLAG (binfo->flags, BGP_INFO_SUSPICIOUS_P);
1845 +          status = BGP_INFO_SUSPICIOUS_P;
1846 +          goto UPP_DONE;
1847 +        }
1848 +    }
1849 +
1850 +  /* Have we seen the prefix recently? */
1851 +  if (pre->lastSeen + pgbgp->prefix_hist_time > t_now)
1852 +    goto UPP_DONE;
1853 +
1854 +#ifndef PGBGP_DEBUG
1855 +  /* Are we within the initial grace period? */
1856 +  if (newPeer)
1857 +    goto UPP_DONE;
1858 +#endif
1859 +
1860 +  /* Is there a less specific *in recent history* that this could be hijacking? */
1861 +  if (supernode == NULL)
1862 +    goto UPP_DONE;
1863 +
1864 +  /* Does this path the super-net's non-anomalous path from this peer?  If so it's okay */
1865 +  int found = false;
1866 +  for (struct bgp_info * ri = supernode->info; ri; ri = ri->next)
1867 +    {
1868 +      if (ri->peer->as == binfo->peer->as)
1869 +       {
1870 +         if (!ANOMALOUS(ri->flags) && bgp_pgbgp_pathIsPrefix(ri->attr->aspath, at->aspath))
1871 +             found = true;
1872 +         break;
1873 +       }
1874 +    }
1875 +
1876 +  if (found)
1877 +    goto UPP_DONE;
1878 +
1879 +  /* 
1880 +     It's not in recent history, and there is a less specific currently in use
1881 +     Response:
1882 +     . Ignore this prefix
1883 +     . Make the less specific's route for this neighbor suspicious
1884 +   */
1885 +
1886 +
1887 +  pre->ignoreUntil = t_now + pgbgp->sub_sus_time;
1888 +
1889 +  struct bgp_pgbgp_pathSet pathOrigins;
1890 +  pathOrigins = bgp_pgbgp_pathOrigin (at->aspath);
1891 +  for (int i = 0; i < pathOrigins.length; i++)
1892 +    bgp_pgbgp_logSubprefixAnomaly (pathOrigins.ases[i], rn, at, supernode);
1893 +
1894 +
1895 +
1896 +  r = XCALLOC (MTYPE_BGP_PGBGP_REUSE, sizeof (struct bgp_pgbgp_reuse));
1897 +  r->type = PGBGP_REUSE_PREFIX;
1898 +  r->deprefUntil = pre->ignoreUntil;
1899 +  r->data.prefix.rn = rn;
1900 +  r->data.prefix.rnsuper = supernode;
1901 +  bgp_lock_node (rn);
1902 +  bgp_lock_node (supernode);
1903 +  pqueue_enqueue (r, pgbgp->reuse_q);
1904 +  pgbgp->rq_size += 1;
1905 +
1906 +UPP_IGNORE:
1907 +  // Sanity check
1908 +  if (supernode == NULL)
1909 +    goto UPP_DONE;
1910 +    
1911 +  /* Set the less specific's route from this peer to suspicious */
1912 +  changed = false;
1913 +
1914 +  for (struct bgp_info * ri = supernode->info; ri; ri = ri->next)
1915 +    {
1916 +      if (ri->peer->as == binfo->peer->as)
1917 +        {
1918 +          if (!CHECK_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P))
1919 +            {
1920 +              SET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P);
1921 +              changed = true;
1922 +            }
1923 +          break;
1924 +        }
1925 +    }
1926 +
1927 +  // Make note of it in the less specific's history information
1928 +  found = false;
1929 +  struct bgp_pgbgp_hist *superhist = supernode->hist;
1930 +
1931 +  if (superhist && superhist->p)
1932 +    {
1933 +      for (struct bgp_pgbgp_avoid * av = superhist->p->avoid; av;
1934 +           av = av->next)
1935 +        {
1936 +          if (av->peerASN == binfo->peer->as)
1937 +            {
1938 +              if (av->avoidUntil < pre->ignoreUntil)
1939 +                av->avoidUntil = pre->ignoreUntil;
1940 +              found = true;
1941 +              break;
1942 +            }
1943 +        }
1944 +      if (!found)
1945 +        {
1946 +          struct bgp_pgbgp_avoid *newavoid =
1947 +            XCALLOC (MTYPE_BGP_PGBGP_AVOID, sizeof (struct bgp_pgbgp_avoid));
1948 +          newavoid->peerASN = binfo->peer->as;
1949 +          newavoid->avoidUntil = pre->ignoreUntil;
1950 +          newavoid->next = superhist->p->avoid;
1951 +          newavoid->sub = rn;
1952 +          bgp_lock_node (rn);
1953 +          superhist->p->avoid = newavoid;
1954 +        }
1955 +    }
1956 +  /* 
1957 +     ignore this route unless the supernet's node
1958 +     is only a placeholder from loaded pgbgp data
1959 +   */
1960 +  if (bgp_pgbgp_shouldIgnore (supernode, bgp_pgbgp_selected (supernode)))
1961 +    {
1962 +      SET_FLAG (binfo->flags, BGP_INFO_IGNORED_P);
1963 +      status = BGP_INFO_IGNORED_P;
1964 +    }
1965 +  if (changed)
1966 +    {
1967 +      struct bgp_info *ri = supernode->info;
1968 +      bgp_process (ri->peer->bgp, supernode, supernode->table->afi,
1969 +                   supernode->table->safi);
1970 +    }
1971 +
1972 +UPP_DONE:
1973 +  pre->lastSeen = t_now;
1974 +
1975 +  return status;
1976 +}
1977 +
1978 +int
1979 +bgp_pgbgp_reusePrefix (struct bgp_pgbgp_r_prefix data)
1980 +{
1981 +  struct bgp_info *ri = NULL;
1982 +
1983 +  time_t t_now = time (NULL);
1984 +
1985 +  // Repreference all routes for this node
1986 +  for (ri = data.rn->info; ri; ri = ri->next)
1987 +    UNSET_FLAG (ri->flags, BGP_INFO_IGNORED_P);
1988 +  ri = data.rn->info;
1989 +
1990 +  // Rerun the decision process
1991 +  if (ri != NULL)
1992 +    bgp_process (ri->peer->bgp, data.rn, data.rn->table->afi,
1993 +                 data.rn->table->safi);
1994 +
1995 +
1996 +  // Remove the avoid nodes from the super
1997 +  struct bgp_pgbgp_hist *superhist = data.rnsuper->hist;
1998 +  if (superhist != NULL && superhist->p != NULL)
1999 +    {
2000 +      struct bgp_pgbgp_avoid *parent = NULL;
2001 +      for (struct bgp_pgbgp_avoid * av = superhist->p->avoid; av;)
2002 +        {
2003 +          int numChanged = 0;
2004 +          if (av->avoidUntil <= t_now)
2005 +            {
2006 +              struct bgp_pgbgp_avoid *del = av;
2007 +              av = av->next;
2008 +              if (parent == NULL)
2009 +                superhist->p->avoid = av;
2010 +              else
2011 +                parent->next = av;
2012 +
2013 +              // Repreference any routes
2014 +              for (ri = data.rnsuper->info; ri; ri = ri->next)
2015 +                {
2016 +                  if (ri->peer->as == del->peerASN)
2017 +                    {
2018 +                      UNSET_FLAG (ri->flags, BGP_INFO_SUSPICIOUS_P);
2019 +                      numChanged += 1;
2020 +                      break;
2021 +                    }
2022 +                }
2023 +              ri = data.rnsuper->info;
2024 +
2025 +              if (numChanged > 0 && ri != NULL)
2026 +                bgp_process (ri->peer->bgp, data.rnsuper,
2027 +                             data.rnsuper->table->afi,
2028 +                             data.rnsuper->table->safi);
2029 +              bgp_unlock_node (del->sub);
2030 +              XFREE (MTYPE_BGP_PGBGP_AVOID, del);
2031 +            }
2032 +          else
2033 +            {
2034 +              parent = av;
2035 +              av = av->next;
2036 +            }
2037 +        }
2038 +    }
2039 +
2040 +  // Remove this prefix from the normal database
2041 +  // if it hasn't been seen in the RIB since the last
2042 +  // storage run
2043 +  /*
2044 +     struct bgp_pgbgp_hist *hist = rn->hist;
2045 +     struct bgp_pgbgp_prefix * pre = hist->p;
2046 +
2047 +     if (pre && pre->lastSeen < pgbgp->lastStore)
2048 +     {
2049 +     // Delete this node
2050 +     for(struct bgp_pgbgp_avoid * av = hist->p->avoid; av;)
2051 +     {
2052 +     struct bgp_pgbgp_avoid *del = av;
2053 +     av = av->next;
2054 +     bgp_unlock_node(del->sub);
2055 +     XFREE (MTYPE_BGP_PGBGP_AVOID, del);
2056 +     }
2057 +     XFREE(MTYPE_BGP_PGBGP_PREFIX, pre);
2058 +     hist->p = NULL;      
2059 +     }
2060 +   */
2061 +  bgp_unlock_node (data.rn);
2062 +  bgp_unlock_node (data.rnsuper);
2063 +  return 0;
2064 +}
2065 +
2066 +/*! --------------- Sub-Prefix Detection ------------------ !*/
2067 +
2068 +
2069 +
2070 +
2071 +
2072 +/* --------------- Edge Detection ------------------ */
2073 +
2074 +static void
2075 +edge_store_clear_iterator (struct hash_backet *backet, void *file)
2076 +{
2077 +  struct bgp_pgbgp_edge *hedge = backet->data;
2078 +}
2079 +
2080 +static void
2081 +edge_store_iterator (struct hash_backet *backet, FILE * file)
2082 +{
2083 +  struct bgp_pgbgp_edge *hedge = backet->data;
2084 +  time_t t_now = time (NULL);
2085 +  if (hedge->deprefUntil > t_now)
2086 +    return;
2087 +  if (hedge->lastSeen + pgbgp->edge_hist_time > t_now)
2088 +    {
2089 +      fprintf (file, "%d %u %u %lld\n", EDGE_ID, hedge->e.a, hedge->e.b,
2090 +               (long long int) hedge->lastSeen);
2091 +    }
2092 +}
2093 +
2094 +
2095 +void
2096 +bgp_pgbgp_storeEdges (struct bgp_table *table, FILE * file)
2097 +{
2098 +  hash_iterate (pgbgp->edgeT,
2099 +                (void (*)(struct hash_backet *, void *))
2100 +                edge_store_iterator, file);
2101 +  return;
2102 +}
2103 +
2104 +
2105 +int
2106 +bgp_pgbgp_restoreEdge (FILE * file)
2107 +{
2108 +  unsigned int a, b;
2109 +  long long int lastSeen;
2110 +  fscanf (file, "%u %u %lld", &a, &b, &lastSeen);
2111 +  struct bgp_pgbgp_edge finder;
2112 +  finder.e.a = a;
2113 +  finder.e.b = b;
2114 +  finder.lastSeen = lastSeen;
2115 +  struct bgp_pgbgp_edge *hedge =
2116 +    hash_get (pgbgp->edgeT, &finder, edge_hash_alloc);
2117 +  hedge->lastSeen = finder.lastSeen;
2118 +  return 0;
2119 +}
2120 +
2121 +unsigned int
2122 +edge_key_make (void *p)
2123 +{
2124 +  struct bgp_pgbgp_edge *pe = p;
2125 +  struct edge *e = &pe->e;
2126 +  return (e->a << 16) + e->b;
2127 +}
2128 +
2129 +static int
2130 +edge_cmp (const void *arg1, const void *arg2)
2131 +{
2132 +
2133 +  const struct edge *e1 = &((const struct bgp_pgbgp_edge *) arg1)->e;
2134 +  const struct edge *e2 = &((const struct bgp_pgbgp_edge *) arg2)->e;
2135 +  if (e1->a == e2->a && e1->b == e2->b)
2136 +    return 1;
2137 +  return 0;
2138 +}
2139 +
2140 +static void *
2141 +edge_hash_alloc (void *arg)
2142 +{
2143 +  struct bgp_pgbgp_edge *hedge =
2144 +    XCALLOC (MTYPE_BGP_PGBGP_EDGE, sizeof (struct bgp_pgbgp_edge));
2145 +  struct bgp_pgbgp_edge *lookup = arg;
2146 +  if (hedge == NULL)
2147 +    return NULL;
2148 +  hedge->e = lookup->e;
2149 +  return hedge;
2150 +}
2151 +
2152 +
2153 +static void
2154 +edge_gc_iterator (struct hash_backet *backet, time_t * time)
2155 +{
2156 +  time_t t_now = *time;
2157 +  struct bgp_pgbgp_edge *hedge = backet->data;
2158 +
2159 +  int collect = false;
2160 +
2161 +  // Collect if we haven't seen it in awhile
2162 +  if (hedge->lastSeen + pgbgp->edge_hist_time <= t_now)
2163 +    collect = true;
2164 +
2165 +  // Collect if it has just gotten out of anomaly stage
2166 +  // but hasn't been in the RIB since the last GC
2167 +  if (hedge->deprefUntil != 0 && hedge->deprefUntil < t_now)
2168 +    {
2169 +      if (hedge->lastSeen < pgbgp->lastgc)
2170 +        collect = true;
2171 +      hedge->deprefUntil = 0;
2172 +    }
2173 +
2174 +  if (collect)
2175 +    {
2176 +      struct bgp_pgbgp_edge *ret = hash_release (pgbgp->edgeT, hedge);
2177 +      assert (ret != NULL);
2178 +      XFREE (MTYPE_BGP_PGBGP_EDGE, hedge);
2179 +    }
2180 +}
2181 +
2182 +
2183 +
2184 +static void
2185 +edge_update_iterator (struct hash_backet *backet, void *v)
2186 +{
2187 +  struct aspath *p = backet->data;
2188 +  time_t t_now = time (NULL);
2189 +  int first = true;
2190 +
2191 +  struct edge cur;
2192 +  cur.a = 0;
2193 +  cur.b = 0;
2194 +  struct assegment *seg;
2195 +  struct bgp_pgbgp_edge *hedge = NULL;
2196 +  for (seg = p->segments; seg; seg = seg->next)
2197 +    {
2198 +      for (int i = 0; i < seg->length; i++)
2199 +        {
2200 +          cur.a = cur.b;
2201 +          cur.b = seg->as[i];
2202 +          if (first)
2203 +            {
2204 +              first = false;
2205 +              continue;
2206 +            }
2207 +          if (cur.a == cur.b)
2208 +            continue;
2209 +          //              printf("%d -- %d\n", cur.a, cur.b);
2210 +          struct bgp_pgbgp_edge finder;
2211 +          finder.e = cur;
2212 +          hedge = hash_lookup (pgbgp->edgeT, &finder);
2213 +
2214 +          if (!hedge)
2215 +            continue;
2216 +          hedge->lastSeen = t_now;
2217 +        }
2218 +    }
2219 +}
2220 +
2221 +int
2222 +bgp_pgbgp_garbageCollectEdges (struct bgp_table *table)
2223 +{
2224 +  // Update the timings
2225 +  hash_iterate (ashash,
2226 +                (void (*)(struct hash_backet *, void *))
2227 +                edge_update_iterator, NULL);
2228 +
2229 +  // Perform the collection
2230 +  time_t t_now = time (NULL);
2231 +  hash_iterate (pgbgp->edgeT,
2232 +                (void (*)(struct hash_backet *, void *))
2233 +                edge_gc_iterator, &t_now);
2234 +  return 0;
2235 +}
2236 +
2237 +static void
2238 +edge_clean_iterator (struct hash_backet *backet, void *a1)
2239 +{
2240 +  struct bgp_pgbgp_edge *hedge = backet->data;
2241 +  struct bgp_pgbgp_edge *ret = hash_release (pgbgp->edgeT, hedge);
2242 +  assert (ret != NULL);
2243 +  XFREE (MTYPE_BGP_PGBGP_EDGE, hedge);
2244 +}
2245 +
2246 +static void
2247 +bgp_pgbgp_cleanEdges (void)
2248 +{
2249 +  if (pgbgp->edgeT != NULL)
2250 +    {
2251 +      hash_iterate (pgbgp->edgeT,
2252 +                    (void (*)(struct hash_backet *, void *))
2253 +                    edge_clean_iterator, NULL);
2254 +      hash_free (pgbgp->edgeT);
2255 +    }
2256 +  return;
2257 +}
2258 +
2259 +void
2260 +bgp_pgbgp_logEdgeAnomaly (struct bgp_node *rn, struct attr *at,
2261 +                          struct edge *edge)
2262 +{
2263 +  assert (pgbgp);
2264 +  if (!pgbgp->anomalies)
2265 +    return;
2266 +  FILE *file = fopen (pgbgp->anomalies, "a");
2267 +  if (!file)
2268 +    return;
2269 +
2270 +  char pre[256];
2271 +  prefix2str (&rn->p, pre, sizeof (pre));
2272 +
2273 +  // EDGE | TIME | NEXTHOP | PREFIX | PATH | Edge.a | Edge.b
2274 +
2275 +  fprintf (file, "%d|%lld|%s|%s|%s|%d|%d\n", EDGE,
2276 +           (long long int) time (NULL), inet_ntoa (at->nexthop), pre,
2277 +           aspath_print (at->aspath), edge->a, edge->b);
2278 +
2279 +  fclose (file);
2280 +}
2281 +
2282 +
2283 +int
2284 +bgp_pgbgp_updateEdge (struct bgp_pgbgp_hist *hist, struct bgp_info *binfo,
2285 +                      struct attr *at, struct bgp_node *rn, time_t t_now,
2286 +                      int newPeer)
2287 +{
2288 +
2289 +  char first = true;
2290 +  struct edge curEdge;
2291 +  curEdge.a = 0;
2292 +  curEdge.b = 0;
2293 +
2294 +
2295 +  if (at->aspath == NULL)
2296 +    return 0;
2297 +  struct assegment *seg = at->aspath->segments;
2298 +  if (seg == NULL)
2299 +    return 0;
2300 +  time_t max_depref = 0;
2301 +  for (seg = at->aspath->segments; seg; seg = seg->next)
2302 +    {
2303 +      for (int i = 0; i < seg->length; i++)
2304 +        {
2305 +          curEdge.a = curEdge.b;
2306 +          curEdge.b = seg->as[i];
2307 +          if (first)
2308 +            {
2309 +              first = false;
2310 +              continue;
2311 +            }
2312 +          if (curEdge.a == curEdge.b)
2313 +            continue;