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
cache_init(int max)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
update_state(struct sc_ent * prev,struct pfsync_state * new,double rate)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
add_state(struct pfsync_state * st)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 *
cache_state(struct pfsync_state * st)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
cache_endupdate(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
sc_cmp(struct sc_ent * a,struct sc_ent * b)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