1 /* $OpenBSD: cache.c,v 1.8 2019/01/17 05:56:29 tedu Exp $ */ 2 /* 3 * Copyright (c) 2001, 2007 Can Erkin Acar <canacar@openbsd.org> 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 #include <sys/types.h> 19 #include <sys/ioctl.h> 20 #include <sys/socket.h> 21 22 #include <net/if.h> 23 #include <netinet/in.h> 24 25 #include <netinet/tcp_fsm.h> 26 #ifdef TEST_COMPAT 27 #include "pfvarmux.h" 28 #else 29 #include <net/pfvar.h> 30 #endif 31 #include <arpa/inet.h> 32 33 #include <stdio.h> 34 #include <stdlib.h> 35 #include <time.h> 36 37 #include <assert.h> 38 39 #include "cache.h" 40 41 /* prototypes */ 42 void update_state(struct sc_ent *, struct pfsync_state *, double); 43 struct sc_ent *cache_state(struct pfsync_state *); 44 static __inline int sc_cmp(struct sc_ent *s1, struct sc_ent *s2); 45 46 /* initialize the tree and queue */ 47 RB_HEAD(sc_tree, sc_ent) sctree; 48 TAILQ_HEAD(sc_queue, sc_ent) scq1, scq2, scq_free; 49 RB_GENERATE(sc_tree, sc_ent, tlink, sc_cmp) 50 51 struct sc_queue *scq_act = NULL; 52 struct sc_queue *scq_exp = NULL; 53 54 int cache_max = 0; 55 int cache_size = 0; 56 57 struct sc_ent *sc_store = NULL; 58 59 /* preallocate the cache and insert into the 'free' queue */ 60 int 61 cache_init(int max) 62 { 63 int n; 64 static int initialized = 0; 65 66 if (max < 0 || initialized) 67 return (1); 68 69 if (max == 0) { 70 sc_store = NULL; 71 } else { 72 sc_store = reallocarray(NULL, max, sizeof(struct sc_ent)); 73 if (sc_store == NULL) 74 return (1); 75 } 76 77 RB_INIT(&sctree); 78 TAILQ_INIT(&scq1); 79 TAILQ_INIT(&scq2); 80 TAILQ_INIT(&scq_free); 81 82 scq_act = &scq1; 83 scq_exp = &scq2; 84 85 for (n = 0; n < max; n++) 86 TAILQ_INSERT_HEAD(&scq_free, sc_store + n, qlink); 87 88 cache_size = cache_max = max; 89 initialized++; 90 91 return (0); 92 } 93 94 void 95 update_state(struct sc_ent *prev, struct pfsync_state *new, double rate) 96 { 97 assert (prev != NULL && new != NULL); 98 prev->t = time(NULL); 99 prev->rate = rate; 100 prev->bytes = COUNTER(new->bytes[0]) + COUNTER(new->bytes[1]); 101 if (prev->peak < rate) 102 prev->peak = rate; 103 } 104 105 void 106 add_state(struct pfsync_state *st) 107 { 108 struct sc_ent *ent; 109 assert(st != NULL); 110 111 if (cache_max == 0) 112 return; 113 114 if (TAILQ_EMPTY(&scq_free)) 115 return; 116 117 ent = TAILQ_FIRST(&scq_free); 118 TAILQ_REMOVE(&scq_free, ent, qlink); 119 120 cache_size--; 121 122 ent->id = st->id; 123 ent->creatorid = st->creatorid; 124 ent->bytes = COUNTER(st->bytes[0]) + COUNTER(st->bytes[1]); 125 ent->peak = 0; 126 ent->rate = 0; 127 ent->t = 0; 128 129 RB_INSERT(sc_tree, &sctree, ent); 130 TAILQ_INSERT_HEAD(scq_act, ent, qlink); 131 } 132 133 /* must be called only once for each state before cache_endupdate */ 134 struct sc_ent * 135 cache_state(struct pfsync_state *st) 136 { 137 struct sc_ent ent, *old; 138 double sd, td, r; 139 140 if (cache_max == 0) 141 return (NULL); 142 143 ent.id = st->id; 144 ent.creatorid = st->creatorid; 145 old = RB_FIND(sc_tree, &sctree, &ent); 146 147 if (old == NULL) { 148 add_state(st); 149 return (NULL); 150 } 151 152 if (COUNTER(st->bytes[0]) + COUNTER(st->bytes[1]) < old->bytes) 153 return (NULL); 154 155 sd = COUNTER(st->bytes[0]) + COUNTER(st->bytes[1]) - old->bytes; 156 td = time(NULL) - old->t; 157 158 if (td > 0) { 159 r = sd/td; 160 update_state(old, st, r); 161 } 162 163 /* move to active queue */ 164 TAILQ_REMOVE(scq_exp, old, qlink); 165 TAILQ_INSERT_HEAD(scq_act, old, qlink); 166 167 return (old); 168 } 169 170 /* remove the states that are not updated in this cycle */ 171 void 172 cache_endupdate(void) 173 { 174 struct sc_queue *tmp; 175 struct sc_ent *ent; 176 177 while (! TAILQ_EMPTY(scq_exp)) { 178 ent = TAILQ_FIRST(scq_exp); 179 TAILQ_REMOVE(scq_exp, ent, qlink); 180 RB_REMOVE(sc_tree, &sctree, ent); 181 TAILQ_INSERT_HEAD(&scq_free, ent, qlink); 182 cache_size++; 183 } 184 185 tmp = scq_act; 186 scq_act = scq_exp; 187 scq_exp = tmp; 188 } 189 190 static __inline int 191 sc_cmp(struct sc_ent *a, struct sc_ent *b) 192 { 193 if (a->id > b->id) 194 return (1); 195 if (a->id < b->id) 196 return (-1); 197 if (a->creatorid > b->creatorid) 198 return (1); 199 if (a->creatorid < b->creatorid) 200 return (-1); 201 return (0); 202 } 203