File: rbldnsd_ip4set.c

package info (click to toggle)
rbldnsd 0.996a
  • links: PTS
  • area: main
  • in suites: etch, etch-m68k
  • size: 468 kB
  • ctags: 799
  • sloc: ansic: 5,704; sh: 349; makefile: 183; awk: 33
file content (446 lines) | stat: -rw-r--r-- 13,481 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
/* $Id: rbldnsd_ip4set.c,v 1.42 2005/12/18 18:43:56 mjt Exp $
 * ip4set dataset type: IP4 addresses (ranges), with A and TXT
 * values for every individual entry.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "rbldnsd.h"

struct entry {
  ip4addr_t addr;	/* key: IP address */
  const char *rr;	/* A and TXT RRs */
};

struct dsdata {
  unsigned n[4];	/* counts */
  unsigned a[4];	/* allocated (only for loading) */
  unsigned h[4];	/* hint, how much to allocate next time */
  struct entry *e[4];	/* entries */
  const char *def_rr;	/* default A and TXT RRs */
};

/* indexes */
#define E32 0
#define E24 1
#define E16 2
#define E08 3
/* ..and masks, "network" and "host" parts */
#define M32 0xffffffffu
#define H32 0x00000000u
#define M24 0xffffff00u
#define H24 0x000000ffu
#define M16 0xffff0000u
#define H16 0x0000ffffu
#define M08 0xff000000u
#define H08 0x00ffffffu

definedstype(ip4set, DSTF_IP4REV, "set of (ip4 range, value) pairs");

static void ds_ip4set_reset(struct dsdata *dsd, int UNUSED unused_freeall) {
  unsigned r;
  for (r = 0; r < 4; ++r) {
    if (!dsd->e[r]) continue;
    free(dsd->e[r]);
    dsd->e[r] = NULL;
    dsd->n[r] = dsd->a[r] = 0;
  }
  dsd->def_rr = NULL;
}

static int
ds_ip4set_addent(struct dsdata *dsd, unsigned idx,
                 ip4addr_t a, unsigned count,
                 const char *rr) {
  struct entry *e = dsd->e[idx];
  ip4addr_t step = 1 << (idx << 3);

  if (dsd->n[idx] + count > dsd->a[idx]) {
    if (!dsd->a[idx])
      dsd->a[idx] = dsd->h[idx] ? dsd->h[idx] : 64;
    while(dsd->n[idx] + count > dsd->a[idx])
      dsd->a[idx] <<= 1;
    e = trealloc(struct entry, e, dsd->a[idx]);
    if (!e)
      return 0;
    dsd->e[idx] = e;
  }

  e += dsd->n[idx];
  dsd->n[idx] += count;
  for(; count--; a += step, ++e) {
    e->addr = a;
    e->rr = rr;
  }

  return 1;
}

static void ds_ip4set_start(struct dataset *ds) {
  ds->ds_dsd->def_rr = def_rr;
}

static int
ds_ip4set_line(struct dataset *ds, char *s, struct dsctx *dsc) {
  struct dsdata *dsd = ds->ds_dsd;
  ip4addr_t a, b;
  const char *rr;
  unsigned rrl;

  int not;
  int bits;

  if (*s == ':') {
    if (!(rrl = parse_a_txt(s, &rr, def_rr, dsc)))
      return 1;
    if (!(dsd->def_rr = mp_dmemdup(ds->ds_mp, rr, rrl)))
      return 0;
    return 1;
  }

  if (*s == '!') {
    not = 1;
    ++s; SKIPSPACE(s);
  }
  else
    not = 0;
  if ((bits = ip4range(s, &a, &b, &s)) <= 0 ||
      (*s && !ISSPACE(*s) && !ISCOMMENT(*s) && *s != ':')) {
    dswarn(dsc, "invalid address");
    return 1;
  }
  if (accept_in_cidr)
    a &= ip4mask(bits);
  else if (a & ~ip4mask(bits)) {
    dswarn(dsc, "invalid range (non-zero host part)");
    return 1;
  }
  if (dsc->dsc_ip4maxrange && dsc->dsc_ip4maxrange <= (b - a)) {
    dswarn(dsc, "too large range (%u) ignored (%u max)",
           b - a + 1, dsc->dsc_ip4maxrange);
    return 1;
  }
  if (not)
    rr = NULL;
  else {
    SKIPSPACE(s);
    if (!*s || ISCOMMENT(*s))
      rr = dsd->def_rr;
    else if (!(rrl = parse_a_txt(s, &rr, dsd->def_rr, dsc)))
      return 1;
    else if (!(rr = mp_dmemdup(ds->ds_mp, rr, rrl)))
      return 0;
  }

  /*XXX some comments about funny ip4range_expand et al */

#define fn(idx,start,count) ds_ip4set_addent(dsd, idx, start, count, rr)

/* helper macro for ip4range_expand:
 * deal with last octet, shifting a and b when done
 */
#define ip4range_expand_octet(bits)			\
  if ((a | 255u) >= b) {				\
    if (b - a == 255u)					\
      return fn((bits>>3)+1, a<<bits, 1);		\
    else						\
      return fn(bits>>3, a<<bits, b - a + 1);		\
  }							\
  if (a & 255u) {					\
    if (!fn(bits>>3, a<<bits, 256u - (a & 255u)))	\
      return 0;						\
    a = (a >> 8) + 1;					\
  }							\
  else							\
    a >>= 8;						\
  if ((b & 255u) != 255u) {				\
    if (!fn((bits>>3), (b & ~255u)<<bits, (b&255u)+1))	\
      return 0;						\
    b = (b >> 8) - 1;					\
  }							\
  else							\
    b >>= 8

  ip4range_expand_octet(0);
  ip4range_expand_octet(8);
  ip4range_expand_octet(16);
  return fn(3, a << 24, b - a + 1);

}

static void ds_ip4set_finish(struct dataset *ds, struct dsctx *dsc) {
  struct dsdata *dsd = ds->ds_dsd;
  unsigned r;
  for(r = 0; r < 4; ++r) {
    if (!dsd->n[r]) {
      dsd->h[r] = 0;
      continue;
    }
    dsd->h[r] = dsd->a[r];
    while((dsd->h[r] >> 1) >= dsd->n[r])
      dsd->h[r] >>= 1;

#   define QSORT_TYPE struct entry
#   define QSORT_BASE dsd->e[r]
#   define QSORT_NELT dsd->n[r]
#   define QSORT_LT(a,b) \
       a->addr < b->addr ? 1 : \
       a->addr > b->addr ? 0 : \
       a->rr < b->rr
#   include "qsort.c"

#define ip4set_eeq(a,b) a.addr == b.addr && rrs_equal(a,b)
    REMOVE_DUPS(struct entry, dsd->e[r], dsd->n[r], ip4set_eeq);
    SHRINK_ARRAY(struct entry, dsd->e[r], dsd->n[r], dsd->a[r]);
  }
  dsloaded(dsc, "e32/24/16/8=%u/%u/%u/%u",
           dsd->n[E32], dsd->n[E24], dsd->n[E16], dsd->n[E08]);
}

static const struct entry *
ds_ip4set_find(const struct entry *e, int b, ip4addr_t q) {
  int a = 0, m;
  --b;
  while(a <= b) {
    if (e[(m = (a + b) >> 1)].addr == q) {
      const struct entry *p = e + m - 1;
      while(p >= e && p->addr == q)
        --p;
      return p + 1;
    }
    else if (e[m].addr < q) a = m + 1;
    else b = m - 1;
  }
  return NULL;
}

static int
ds_ip4set_query(const struct dataset *ds, const struct dnsqinfo *qi,
                struct dnspacket *pkt) {
  const struct dsdata *dsd = ds->ds_dsd;
  ip4addr_t q = qi->qi_ip4;
  ip4addr_t f;
  const struct entry *e, *t;
  const char *ipsubst;

  if (!qi->qi_ip4valid) return 0;
  check_query_overwrites(qi);

#define try(i,mask) \
 (dsd->n[i] && \
  (t = dsd->e[i] + dsd->n[i], \
   e = ds_ip4set_find(dsd->e[i], dsd->n[i], (f = q & mask))) != NULL)

  if (!try(E32, M32) &&
      !try(E24, M24) &&
      !try(E16, M16) &&
      !try(E08, M08))
    return 0;

  if (!e->rr) return 0;		/* exclusion */

  ipsubst = (qi->qi_tflag & NSQUERY_TXT) ? ip4atos(q) : NULL;
  do addrr_a_txt(pkt, qi->qi_tflag, e->rr, ipsubst, ds);
  while(++e < t && e->addr == f);

  return NSQUERY_FOUND;
}

#ifndef NO_MASTER_DUMP

/* dump the data as master-format file.
 * Having two entries:
 *    127.0.0.0/8  "A"
 *    127.0.0.2    "B"
 * we have to generate the following stuff to make bind return what we need:
 *         *.127 "A"
 *       *.0.127 "A"
 *     *.0.0.127 "A"
 *     2.0.0.127 "B"
 * If we have two (or more) /8 entries, each should be repeated for /16 and /24.
 * The same is when we have /16 and /32 (no /24), or /8 and /24 (no /16).
 *
 * The algorithm is as follows.  We enumerating entries in /8 array
 * (ds_ip4set_dump08()), emitting all "previous" entries in /16 (indicating
 * there's no parent entry), when all entries in lower levels that are
 * covered by our /16 (indicating there IS a parent this time), our own /16
 * group -- all entries with the same address.  ds_ip4set_dump16() accepts
 * 'last' parameter telling it at which address to stop).  ds_ip4set_dump16()
 * does the same with /16s and /24s as ds_ip4set_dump08() does with /8s and
 * /16s.  Similarily, ds_ip4set_dump24() deals with /24s and /32s, but at this
 * point, it should pay attention to the case when there's a /8 but no /16
 * covering the range in question.  Ditto for ds_ip4set_dump32(), which also
 * should handle the case when there's no upper /24 but either /16 or /8 exists.
 */

struct dumpdata {		/* state. */
  const struct entry *e[4];	/* current entry we're looking at in each arr */
  const struct entry *t[4];	/* end pointers for arrays */
  const struct dataset *ds;	/* the dataset in question */
  FILE *f;			/* file to dump data to */
};

/* dump a group of entries with the same IP address.
 * idx shows how many octets we want to print --
 * used only with E08, E16 or E24, not with E32.
 * e is where to start, and t is the end of the array.
 * Returns pointer to the next element after the group.
 */
static const struct entry *
ds_ip4set_dump_group(const struct dumpdata *dd,
                     ip4addr_t saddr, ip4addr_t hmask,
                     const struct entry *e, const struct entry *t) {
  ip4addr_t addr = e->addr;
  do
    dump_ip4range(saddr, saddr | hmask, e->rr, dd->ds, dd->f);
  while(++e < t && e->addr == addr);
  return e;
}

/* dump all /32s up to addr <= last.
 * u08, u16 and u24 is what's on upper levels. */
static void
ds_ip4set_dump32(struct dumpdata *dd, ip4addr_t last,
                 const struct entry *u08, const struct entry *u16,
                 const struct entry *u24) {
  const struct entry *e = dd->e[E32], *t = dd->t[E32];
  ip4addr_t m16 = 1, m24 = 1;
  /* up_rr is true if there's anything non-excluded that is on upper level. */
  int up_rr = (u24 ? u24->rr : u16 ? u16->rr : u08 ? u08->rr : NULL) != NULL;
  while(e < t && e->addr <= last) {
    if (!e->rr && !up_rr) {
      /* skip entry if nothing listed on upper level */
      ++e;
      continue;
    }
    if (!u24 && m24 != (e->addr & M24) && (u08 || u16)) {
      /* if there's no "parent" /24 entry, AND
       * we just advanced to next /24, AND
       * there's something on even-upper levels,
       * we have to repeat something from upper-upper level
       * in mid-level. */
      m24 = e->addr & M24; /* remember parent /24 mask we're in */
      if (!u16 && m16 != (m24 & M16) && u08) {
        /* if there's no parent /16, but there is parent /8:
         * repeat that /8 in current /16, but only once per /16. */
        m16 = m24 & M16;
        ds_ip4set_dump_group(dd, m16, H16, u08, dd->t[E08]);
      }
      /* several cases:
         u16!=0 and isn't exclusion: dump it in upper /24.
         u16!=0 and it IS exclusion: do nothing.
         u08!=0 - dump it.
      */
      if (!u16)			/* u08 is here as per condition above */
        ds_ip4set_dump_group(dd, m24, H24, u08, dd->t[E08]);
      else if (u16->rr)
        ds_ip4set_dump_group(dd, m24, H24, u16, dd->t[E16]);
      /* else nothing: the upper-upper /16 is an exclusion anyway */
    }
    dump_ip4(e->addr, e->rr, dd->ds, dd->f);
    ++e;
  }
  dd->e[E32] = e;
}

/* dump all /24s and lower-levels up to addr <= last.
 * u08 and u16 is what's on upper levels. */
static void
ds_ip4set_dump24(struct dumpdata *dd, ip4addr_t last,
                 const struct entry *u08, const struct entry *u16) {
  const struct entry *e = dd->e[E24], *t = dd->t[E24];
  ip4addr_t m16 = 1, a;
  /* up_rr is true if there's a non-excluded upper-level entry present */
  int up_rr = (u16 ? u16->rr : u08 ? u08->rr : NULL) != NULL;
  while(e < t && (a = e->addr) <= last) {
    if (!e->rr && !up_rr) {
      /* ignore exclusions if there's nothing listed in upper levels */
      ++e;
      continue;
    }
    if (a)
      /* dump all preceeding lower-level entries */
      ds_ip4set_dump32(dd, a - 1, u08, u16, 0);
    /* and this is where the fun is. */
    if (!u16 && m16 != (a & M16) && u08) {
      /* if there's no "parent" /16 entry, AND
       * we just advanced to next /16, AND
       * there's a /8 entry,
       * repeat that /8 in this new /16.
       * This produces *.x.y entry from y/8 and y.x.z/24. */
      m16 = a & M16;
      ds_ip4set_dump_group(dd, m16, H16, u08, dd->t[E08]);
    }
    /* dump all lower-level entries covering by our group */
    ds_ip4set_dump32(dd, a | H24, u08, u16, e);
    /* dump our group */
    e = ds_ip4set_dump_group(dd, a, H24, e, t);
  }
  /* and finally, dump the rest in lower-level groups up to last */
  ds_ip4set_dump32(dd, last, u08, u16, 0);
  dd->e[E24] = e;		/* save loop counter */
}

/* dump all /16s and lower-levels up to addr <= last.
 * u08 is what's on upper levels. */
static void
ds_ip4set_dump16(struct dumpdata *dd, ip4addr_t last,
                 const struct entry *u08) {
  const struct entry *e = dd->e[E16], *t = dd->t[E16];
  while(e < t && e->addr <= last) {
    if (!e->rr && !u08) {
      /* skip exclusion only if there's no upper-level entry */
      ++e;
      continue;
    }
    if (e->addr)
      /* dump all preceeding lower-level entries if any */
      ds_ip4set_dump24(dd, e->addr - 1, u08, 0);
    /* dump all lower-level entries covering by this group */
    ds_ip4set_dump24(dd, e->addr | H16, u08, e);
    /* dump the group itself */
    e = ds_ip4set_dump_group(dd, e->addr, H16, e, t);
  }
  /* and finally, dump the rest in lower levels, up to last */
  ds_ip4set_dump24(dd, last, u08, 0);
  dd->e[E16] = e;		/* update loop variable */
}

/* ok, the simplest case, dump all /8s in turn, unconditionally */
static void
ds_ip4set_dump08(struct dumpdata *dd) {
  const struct entry *e = dd->e[E08], *t = dd->t[E08];
  while(e < t) {
    if (!e->rr) {
      /* just skip all excludes here */
      ++e;
      continue;
    }
    if (e->addr)
      /* dump any preceeding lower-level entries if any */
      ds_ip4set_dump16(dd, e->addr - 1, 0);
    /* dump all entries covered by our group */
    ds_ip4set_dump16(dd, e->addr | H08, e);
    /* dump our own group too */
    e = ds_ip4set_dump_group(dd, e->addr, H08, e, t);
  }
  /* and finally, dump the rest */
  ds_ip4set_dump16(dd, M32, 0);
  dd->e[E08] = e;		/* just in case ;) */
}

static void
ds_ip4set_dump(const struct dataset *ds,
               const unsigned char UNUSED *unused_odn,
               FILE *f) {
  struct dumpdata dd;
  const struct dsdata *dsd = ds->ds_dsd;
  unsigned i;
  for(i = 0; i < 4; ++i)
    dd.t[i] = (dd.e[i] = dsd->e[i]) + dsd->n[i];
  dd.ds = ds;
  dd.f = f;
  ds_ip4set_dump08(&dd);
}
#endif /* NO_MASTER_DUMP */