LordOS — a free, fast and secure GNU/Linux distribution based on Debian, with its own desktop environment: display server and Wayland compositor in C, a React UI engine on QuickJS, and private native apps.
C cdebiandesktop-environmentebpffirewalllandlocklinuxlinux-distributionopen-sourceprivacyquickjsraspberry-pi-5reactsecuritywaylandwayland-compositor
/* fwlists.c — subscribed blocklists: raw parsers, the set and the compiled file (see fwlists.h). */
#include "fwlists.h"
#include "fwmap.h"
#include "rules.h"
#include <arpa/inet.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* The set keeps no names: a name is its 64-bit hash (fw_hash, seeded per process, so nobody can
* craft a name that collides on purpose), sorted for binary search, with the tag of the list it
* came from. A list of 380,000 names takes about 4 MB instead of 50. Networks are kept whole. */
typedef struct { uint64_t h; uint32_t seq; uint16_t tag; uint16_t pad; } NameEnt;
typedef struct { unsigned char k[18]; uint16_t tag; uint32_t seq; } NetEnt;
struct FwLists {
NameEnt *ex, *sub; /* exact names; names with every subdomain */
size_t nex, nsub, capex, capsub;
NetEnt *net;
size_t nnet, capnet;
uint32_t seq;
int sorted; /* 0: entries were added since the last sort */
unsigned char has4[33], has6[129]; /* prefix lengths present */
};
FwLists *fwl_new(void) { return calloc(1, sizeof(FwLists)); }
void fwl_free(FwLists *l) {
if (!l) return;
free(l->ex);
free(l->sub);
free(l->net);
free(l);
}
FwlFormat fwl_format_from_name(const char *n) {
if (!n) return 0;
if (!strcmp(n, "hosts")) return FWL_FMT_HOSTS;
if (!strcmp(n, "domains")) return FWL_FMT_DOMAINS;
if (!strcmp(n, "ips")) return FWL_FMT_IPS;
return 0;
}
/* ---- the set ---- */
static size_t net_key(int fam, const uint8_t *addr, int prefix, unsigned char *k) {
memset(k, 0, 18);
k[0] = (unsigned char)fam;
k[1] = (unsigned char)prefix;
int bytes = fam == 4 ? 4 : 16;
for (int i = 0; i < bytes; i++) {
int bits = prefix - i * 8;
unsigned char m = bits >= 8 ? 0xff : bits <= 0 ? 0 : (unsigned char)(0xff << (8 - bits));
k[2 + i] = addr[i] & m;
}
return 18;
}
static int name_cmp(const void *a, const void *b) {
const NameEnt *x = a, *y = b;
if (x->h != y->h) return x->h < y->h ? -1 : 1;
return x->seq < y->seq ? -1 : x->seq > y->seq;
}
static int net_cmp(const void *a, const void *b) {
const NetEnt *x = a, *y = b;
int c = memcmp(x->k, y->k, 18);
if (c) return c;
return x->seq < y->seq ? -1 : x->seq > y->seq;
}
/* Sorts and drops repeated entries (the first one added keeps its tag). Returns how many went. */
static size_t uniq_names(NameEnt *v, size_t *n) {
if (*n < 2) return 0;
qsort(v, *n, sizeof *v, name_cmp);
size_t w = 1;
for (size_t i = 1; i < *n; i++) if (v[i].h != v[w - 1].h) v[w++] = v[i];
size_t gone = *n - w;
*n = w;
return gone;
}
static size_t finish(FwLists *l) {
if (!l || l->sorted) return 0;
size_t gone = uniq_names(l->ex, &l->nex) + uniq_names(l->sub, &l->nsub);
if (l->nnet > 1) {
qsort(l->net, l->nnet, sizeof *l->net, net_cmp);
size_t w = 1;
for (size_t i = 1; i < l->nnet; i++) if (memcmp(l->net[i].k, l->net[w - 1].k, 18)) l->net[w++] = l->net[i];
gone += l->nnet - w;
l->nnet = w;
}
l->sorted = 1;
return gone;
}
size_t fwl_finish(FwLists *l) { return finish(l); }
size_t fwl_domains(const FwLists *l) { if (!l) return 0; finish((FwLists *)l); return l->nex + l->nsub; }
size_t fwl_nets(const FwLists *l) { if (!l) return 0; finish((FwLists *)l); return l->nnet; }
static int grow(void **v, size_t *cap, size_t n, size_t sz) {
if (n < *cap) return 0;
size_t c = *cap ? *cap * 2 : 1024;
void *p = realloc(*v, c * sz);
if (!p) return -1;
*v = p;
*cap = c;
return 0;
}
/* A name with at least one dot, normalized; 0 ok. */
static int good_name(const char *in, size_t n, char *out) {
char tmp[FW_NAME_MAX + 2];
if (!n || n > FW_NAME_MAX) return -1;
memcpy(tmp, in, n);
tmp[n] = 0;
if (fw_norm_domain(tmp, out)) return -1;
return strchr(out, '.') ? 0 : -1;
}
static int parse_net(const char *s, size_t n, FwRule *r) {
char tmp[80];
if (!n || n >= sizeof tmp) return -1;
memcpy(tmp, s, n);
tmp[n] = 0;
if (!strchr(tmp, ':') && !strchr(tmp, '/') && !strchr(tmp, '.')) return -1;
if (fw_parse_dest(tmp, r) || r->kind != FW_DST_CIDR) return -1;
return 0;
}
/* Networks a blocklist may never carry: the LAN (it would cut this machine off its own network)
* and anything broader than /8 (IPv4) or /16 (IPv6). */
static int net_usable(const FwRule *r) {
if (r->prefix < (r->fam == 4 ? 8 : 16)) return 0;
return !fw_addr_is_lan(r->fam, r->addr);
}
/* What a line is: 'd'/'s' with the name in name, 'n' with the network in r, or 0 if invalid. */
static int check_line(const char *line, size_t len, char *name, FwRule *r) {
if (!line || len < 3 || line[1] != ' ') return 0;
const char *v = line + 2;
size_t vn = len - 2;
if (line[0] == 'd' || line[0] == 's') {
if (good_name(v, vn, name) || strlen(name) != vn || memcmp(name, v, vn)) return 0; /* already normalized */
return line[0];
}
if (line[0] == 'n') return !parse_net(v, vn, r) && net_usable(r) ? 'n' : 0;
return 0;
}
int fwl_check_line(const char *line, size_t len) {
char name[FW_NAME_MAX];
FwRule r;
return check_line(line, len, name, &r) ? 0 : -1;
}
int fwl_add_line(FwLists *l, const char *line, size_t len, uint16_t tag) {
char name[FW_NAME_MAX];
FwRule r;
if (!l || !tag) return -1;
int kind = check_line(line, len, name, &r);
if (!kind) return -1;
if (kind == 'n') {
if (l->nnet >= FWL_MAX_NETS * 2 || grow((void **)&l->net, &l->capnet, l->nnet, sizeof *l->net)) return -2;
NetEnt *e = &l->net[l->nnet++];
net_key(r.fam, r.addr, r.prefix, e->k);
e->tag = tag;
e->seq = l->seq++;
if (r.fam == 4) l->has4[r.prefix] = 1;
else l->has6[r.prefix] = 1;
} else {
int sub = kind == 's';
NameEnt **v = sub ? &l->sub : &l->ex;
size_t *n = sub ? &l->nsub : &l->nex, *cap = sub ? &l->capsub : &l->capex;
if (l->nex + l->nsub >= FWL_MAX_DOMAINS * 2 || grow((void **)v, cap, *n, sizeof **v)) return -2;
NameEnt *e = &(*v)[(*n)++];
e->h = fw_hash(name, strlen(name));
e->tag = tag;
e->seq = l->seq++;
e->pad = 0;
}
l->sorted = 0;
return 0;
}
long fwl_add_text(FwLists *l, const char *text, size_t len, uint16_t tag) {
long added = 0;
for (size_t i = 0; i < len;) {
const char *nl = memchr(text + i, '\n', len - i);
size_t e = nl ? (size_t)(nl - text) : len;
if (e > i) {
int r = fwl_add_line(l, text + i, e - i, tag);
if (r == -1) return -1;
if (r == -2) break;
added++;
}
i = e + 1;
}
finish(l);
/* the caps are on unique entries */
if (l->nex + l->nsub > FWL_MAX_DOMAINS) l->nsub = l->nex >= FWL_MAX_DOMAINS ? 0 : FWL_MAX_DOMAINS - l->nex;
if (l->nex > FWL_MAX_DOMAINS) l->nex = FWL_MAX_DOMAINS;
if (l->nnet > FWL_MAX_NETS) l->nnet = FWL_MAX_NETS;
return added;
}
FwLists *fwl_load_text(const char *text, size_t len, char *err, size_t errlen) {
size_t hl = strlen(FWL_HEADER);
if (!text || len > FWL_FILE_MAX || memchr(text, 0, len)) { snprintf(err, errlen, "not a list file"); return NULL; }
if (len < hl || memcmp(text, FWL_HEADER, hl) || (len > hl && text[hl] != '\n')) { snprintf(err, errlen, "no header"); return NULL; }
FwLists *l = fwl_new();
if (!l) { snprintf(err, errlen, "out of memory"); return NULL; }
size_t i = hl + 1, lineno = 1;
while (i < len) {
const char *nl = memchr(text + i, '\n', len - i);
size_t e = nl ? (size_t)(nl - text) : len;
lineno++;
int r = e > i ? fwl_add_line(l, text + i, e - i, 1) : 0;
if (r == -1 || r == -2) {
snprintf(err, errlen, r == -2 ? "too many entries (line %zu)" : "invalid line %zu", lineno);
fwl_free(l);
return NULL;
}
i = e + 1;
}
finish(l);
if (l->nex + l->nsub > FWL_MAX_DOMAINS || l->nnet > FWL_MAX_NETS) { snprintf(err, errlen, "too many entries"); fwl_free(l); return NULL; }
return l;
}
static uint16_t find_name(const NameEnt *v, size_t n, uint64_t h) {
size_t lo = 0, hi = n;
while (lo < hi) {
size_t m = lo + (hi - lo) / 2;
if (v[m].h < h) lo = m + 1;
else hi = m;
}
return lo < n && v[lo].h == h ? v[lo].tag : 0;
}
uint16_t fwl_match_name(const FwLists *l, const char *in) {
if (!l || !in) return 0;
finish((FwLists *)l);
if (!l->nex && !l->nsub) return 0;
char name[FW_NAME_MAX];
if (strnlen(in, FW_NAME_MAX + 1) > FW_NAME_MAX || fw_norm_domain(in, name)) return 0;
uint16_t t = find_name(l->ex, l->nex, fw_hash(name, strlen(name)));
if (t) return t;
for (const char *sfx = name; sfx;) {
t = find_name(l->sub, l->nsub, fw_hash(sfx, strlen(sfx)));
if (t) return t;
sfx = strchr(sfx, '.');
if (sfx) sfx++;
}
return 0;
}
uint16_t fwl_match_addr(const FwLists *l, int fam, const uint8_t *addr) {
if (!l || !addr || (fam != 4 && fam != 6)) return 0;
finish((FwLists *)l);
if (!l->nnet) return 0;
uint8_t a[16] = { 0 };
static const uint8_t mapped[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff };
if (fam == 6 && !memcmp(addr, mapped, 12)) { fam = 4; memcpy(a, addr + 12, 4); }
else memcpy(a, addr, fam == 4 ? 4 : 16);
const unsigned char *has = fam == 4 ? l->has4 : l->has6;
for (int p = fam == 4 ? 32 : 128; p >= 0; p--) {
if (!has[p]) continue;
unsigned char k[18];
net_key(fam, a, p, k);
size_t lo = 0, hi = l->nnet;
while (lo < hi) {
size_t m = lo + (hi - lo) / 2;
if (memcmp(l->net[m].k, k, 18) < 0) lo = m + 1;
else hi = m;
}
if (lo < l->nnet && !memcmp(l->net[lo].k, k, 18)) return l->net[lo].tag;
}
return 0;
}
void fwl_net_each(const FwLists *l, int (*cb)(void *u, int fam, const uint8_t *addr, int prefix), void *u) {
if (!l) return;
finish((FwLists *)l);
for (size_t i = 0; i < l->nnet; i++) {
uint8_t a[16] = { 0 };
memcpy(a, l->net[i].k + 2, l->net[i].k[0] == 4 ? 4 : 16);
if (cb(u, l->net[i].k[0], a, l->net[i].k[1])) return;
}
}
uint16_t fwl_block_names(const FwLists *l, const char *const *names, int n) {
uint16_t first = 0;
for (int i = 0; i < n; i++) {
uint16_t t = fwl_match_name(l, names[i]);
if (!t) return 0; /* an unlisted name shares the address */
if (!first) first = t;
}
return first;
}
/* ---- raw lists ------------------------------------------------------------------------------- */
static int is_space(char c) { return c == ' ' || c == '\t' || c == '\r' || c == '\v' || c == '\f'; }
/* Names a hosts file maps to itself, not blocklist entries. */
static int hosts_noise(const char *name) {
static const char *const v[] = { "localhost", "localhost.localdomain", "local", "broadcasthost", "ip6-localhost",
"ip6-loopback", "ip6-localnet", "ip6-mcastprefix", "ip6-allnodes", "ip6-allrouters",
"ip6-allhosts", "0.0.0.0", NULL };
for (int i = 0; v[i]; i++) if (!strcmp(name, v[i])) return 1;
return 0;
}
/* The sink-hole addresses a hosts-format blocklist points names to. */
static int hosts_target(const char *s, size_t n) {
static const char *const v[] = { "0.0.0.0", "127.0.0.1", "::", "::1", NULL };
for (int i = 0; v[i]; i++) if (strlen(v[i]) == n && !memcmp(s, v[i], n)) return 1;
return 0;
}
static int set_err(char *err, size_t errlen, const char *code) {
if (err && errlen) snprintf(err, errlen, "%s", code);
return -1;
}
/* What the parser writes: the normalized lines, each once (a set of their hashes). */
typedef struct {
char *p;
size_t n, cap;
uint64_t *set;
size_t nset, capset; /* capset: a power of 2 */
int err;
} Raw;
static void raw_put(Raw *o, const char *s, size_t n) {
if (o->err) return;
if (o->n + n + 2 > o->cap) {
size_t c = o->cap ? o->cap : 65536;
while (c < o->n + n + 2) c *= 2;
char *p = realloc(o->p, c);
if (!p) { o->err = 1; return; }
o->p = p;
o->cap = c;
}
memcpy(o->p + o->n, s, n);
o->n += n;
o->p[o->n] = 0;
}
/* 1 if new (and now remembered), 0 if already there, -1 out of memory. */
static int raw_seen(Raw *o, uint64_t h) {
if (!h) h = 1;
if ((o->nset + 1) * 2 > o->capset) {
size_t c = o->capset ? o->capset * 2 : 4096;
uint64_t *v = calloc(c, sizeof *v);
if (!v) return -1;
for (size_t i = 0; i < o->capset; i++) {
if (!o->set[i]) continue;
size_t k = (size_t)o->set[i] & (c - 1);
while (v[k]) k = (k + 1) & (c - 1);
v[k] = o->set[i];
}
free(o->set);
o->set = v;
o->capset = c;
}
size_t k = (size_t)h & (o->capset - 1);
while (o->set[k]) {
if (o->set[k] == h) return 0;
k = (k + 1) & (o->capset - 1);
}
o->set[k] = h;
o->nset++;
return 1;
}
static int raw_line(Raw *o, const char *line, size_t n, size_t *count, FwlStats *st) {
int r = raw_seen(o, fw_hash(line, n));
if (r < 0) { o->err = 1; return -1; }
if (!r) { st->dups++; return 0; }
raw_put(o, line, n);
raw_put(o, "\n", 1);
(*count)++;
return 1;
}
/* One name from a list: written (d/s) or counted as why not. 1 written, 0 not, -1 stop. */
static int raw_name(Raw *o, const char *s, size_t n, int sub, FwlStats *st) {
char name[FW_NAME_MAX];
if (n > 2 && s[0] == '*' && s[1] == '.') { s += 2; n -= 2; sub = 1; }
if (n > 3 && s[0] == '|' && s[1] == '|' && s[n - 1] == '^') { s += 2; n -= 3; sub = 1; }
char tmp[FW_NAME_MAX + 2];
if (!n || n > FW_NAME_MAX) { st->bad++; return 0; }
memcpy(tmp, s, n);
tmp[n] = 0;
for (char *c = tmp; *c; c++) if (*c >= 'A' && *c <= 'Z') *c = (char)(*c - 'A' + 'a');
if (hosts_noise(tmp)) { st->skipped++; return 0; }
if (fw_norm_domain(tmp, name)) { st->bad++; return 0; }
if (!strchr(name, '.') || hosts_noise(name)) { st->skipped++; return 0; }
if (st->domains >= FWL_LIST_DOMAINS) return -1;
char line[FW_NAME_MAX + 4];
int ln = snprintf(line, sizeof line, "%c %s", sub ? 's' : 'd', name);
return raw_line(o, line, (size_t)ln, &st->domains, st);
}
static int raw_net(Raw *o, const char *s, size_t n, FwlStats *st) {
FwRule r;
if (parse_net(s, n, &r)) { st->bad++; return 0; }
if (!net_usable(&r)) { st->skipped++; return 0; }
if (st->nets >= FWL_LIST_NETS) return -1;
char ip[INET6_ADDRSTRLEN], line[80];
inet_ntop(r.fam == 4 ? AF_INET : AF_INET6, r.addr, ip, sizeof ip);
int ln = r.prefix == (r.fam == 4 ? 32 : 128) ? snprintf(line, sizeof line, "n %s", ip) : snprintf(line, sizeof line, "n %s/%d", ip, r.prefix);
return raw_line(o, line, (size_t)ln, &st->nets, st);
}
int fwl_parse_raw(const char *raw, size_t len, FwlFormat fmt, int sub, char **out, size_t *outlen,
FwlStats *st, char *err, size_t errlen) {
FwlStats z = { 0 };
if (!st) st = &z;
memset(st, 0, sizeof *st);
*out = NULL;
*outlen = 0;
if (fmt != FWL_FMT_HOSTS && fmt != FWL_FMT_DOMAINS && fmt != FWL_FMT_IPS) return set_err(err, errlen, "format");
if (len > FWL_RAW_MAX) return set_err(err, errlen, "big");
if (memchr(raw, 0, len)) return set_err(err, errlen, "nul");
Raw o = { 0 };
Raw *l = &o;
int full = 0;
size_t i = 0;
/* a UTF-8 byte order mark at the start */
if (len >= 3 && (unsigned char)raw[0] == 0xef && (unsigned char)raw[1] == 0xbb && (unsigned char)raw[2] == 0xbf) i = 3;
while (i < len && !full) {
const char *nl = memchr(raw + i, '\n', len - i);
size_t e = nl ? (size_t)(nl - raw) : len;
if (e - i > FWL_LINE_MAX) { free(o.p); free(o.set); return set_err(err, errlen, "line"); }
const char *s = raw + i;
size_t n = e - i;
i = e + 1;
/* comments: whole-line (#, !, ;) and, after a space, inline (#) */
while (n && is_space(*s)) { s++; n--; }
if (!n || *s == '#' || *s == '!' || *s == ';' || (n >= 2 && s[0] == '/' && s[1] == '/')) continue;
for (size_t k = 1; k < n; k++) if (s[k] == '#' && is_space(s[k - 1])) { n = k; break; }
if (fmt == FWL_FMT_IPS) for (size_t k = 0; k < n; k++) if (s[k] == ';') { n = k; break; }
while (n && is_space(s[n - 1])) n--;
if (!n) continue;
st->lines++;
/* tokens */
const char *tok[16];
size_t tl[16];
int nt = 0, over = 0;
for (size_t k = 0; k < n;) {
while (k < n && is_space(s[k])) k++;
if (k >= n) break;
size_t b = k;
while (k < n && !is_space(s[k])) k++;
if (nt == 16) { over = 1; break; }
tok[nt] = s + b;
tl[nt++] = k - b;
}
for (size_t k = 0; k < n; k++) if ((unsigned char)s[k] < 0x20 && !is_space(s[k])) { over = 1; break; }
if (over || !nt) { st->bad++; continue; }
int r = 0;
if (fmt == FWL_FMT_HOSTS) {
if (nt < 2 || !hosts_target(tok[0], tl[0])) { st->bad++; continue; }
for (int t = 1; t < nt && r >= 0; t++) r = raw_name(l, tok[t], tl[t], sub, st);
} else if (fmt == FWL_FMT_DOMAINS) {
if (nt != 1) { st->bad++; continue; }
r = raw_name(l, tok[0], tl[0], sub, st);
} else {
r = raw_net(l, tok[0], tl[0], st); /* other columns (counts, dates) are ignored */
}
if (r < 0) { full = 1; st->truncated = !o.err; }
}
free(o.set);
if (o.err) { free(o.p); return set_err(err, errlen, "oom"); }
if (st->bad > 20 && st->bad * 10 > st->lines) { free(o.p); return set_err(err, errlen, "format"); }
if (!st->domains && !st->nets) { free(o.p); return set_err(err, errlen, "empty"); }
*out = o.p;
*outlen = o.n;
return 0;
}