crda: few more updates
v2 cover crda: few more updates
Here's a second spin, after quite a bit more testing I ran into a few small issues with the parser and library. This has these additional fixes / enhancements:
* Lifts the restriction on 32 rules, although the kernel is limited by this we don't adhere to this limit on our stream parser or optimizer
* The union code got updated to address two cases that are invalid for unions
* A few fixes on db2rd and optimizer on using the stream parser, if its NULL, bail, we weren't checking for it
* The optimizer was not considering band differences as part of its key broker (when it decides it can use two rules for optimization), to address this we deduce the band and add that to the key mixing. Note that this will need to be updated upon new frequency band additions. This limits the scope of optimizations between their own respective bands.
I've also gone ahead and tested this with a huge fluffy non optimized regulatory domain of 40 rules, and also with the wireless-regdb db.txt. I'll send some optimizations based on this for wireless-regdb.
The only patches that go modified are the stream parser and the optimizer.
Luis R. Rodriguez (6):
crda: relicense under copyleft-next-0.3.0
crda: fix -pedantic gcc compilation
crda: add regulatory domain stream parser
crda: add regulatory domain optimizer
crda: make ssl keys include stdint.h
crda: make reglib a shared library
LICENSE | 14 +- Makefile | 54 +++- copyleft-next-0.3.0 | 219 ++++++++++++++ crda.c | 4 +- db2rd.c | 32 ++ optimize.c | 40 +++ reglib.c | 839 ++++++++++++++++++++++++++++++++++++++++++++++++++++ reglib.h | 60 ++++ utils/key2pub.py | 2 + 9 files changed, 1252 insertions(+), 12 deletions(-) create mode 100644 copyleft-next-0.3.0 create mode 100644 db2rd.c create mode 100644 optimize.c
Signature · 1 line
1.8.4.rc3
PATCH v2 1/6 crda: relicense under copyleft-next-0.3.0
I'm relicensing CRDA to copyleft-next-0.3.0. The original motivation was to help with the BSD family but they are not using any of this software and as this software grows I'd like to ensure we use the best free software license possible.
Fontana's work on copyleft-next is great and has good community traction. At this point development for copyleft-next has slowed down as copyleft-next-0.3.0 is already a good, usable alternative to GPLv2 and GPLv3.
A few notes:
* With copyleft we don't have to specify 'at your option any later version' since the license allows that by default.
* Some folks might wonder if copyleft-next-0.3.0 is OSI OSD-conformant or FSF-free since neither of those bodies have examined the license officially, but note, although IANAL, that copyleft-next is outbound-compatible with GPLv2 and GPLv3
--- LICENSE | 14 +++- copyleft-next-0.3.0 | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 232 insertions(+), 1 deletion(-) create mode 100644 copyleft-next-0.3.0
LICENSE +13 -1
@@ -1,4 +1,16 @@ -Copyright (c) 2008, Luis R. Rodriguez <[email protected]> +Copyright (c) 2013, Luis R. Rodriguez <[email protected]> + +CRDA is licensed under copyleft-next 0.3.0 + +Refer to copyleft-next-0.3.0 for license details, you can +also always get the latest updates of copyleft-next from: + +https://gitorious.org/copyleft-next/ + +This file incorporates work covered by the following copyright and +permission notice: + +Copyright (c) 2008, Luis R. Rodriguez <[email protected]> Copyright (c) 2008, Johannes Berg <[email protected]> Copyright (c) 2008, Michael Green <[email protected]>
copyleft-next-0.3.0 new file +219 -0
219 lines not on this page · raw message
Signature · 1 line
1.8.4.rc3
PATCH v2 2/6 crda: fix -pedantic gcc compilation
In reply to Luis R. Rodriguezgcc likes to complain about this, fix that as we're going to get a bit more anal with code here soon as we're moving towards making a library out of reglib.
--- crda.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
crda.c +3 -1
@@ -141,13 +141,15 @@ int main(int argc, char **argv) {int fd =-1 ;int i =0 , j, r; -char alpha2[3 ] = {};/* NUL-terminate */ +char alpha2[3 ];char *env_country;struct nl80211_state nlstate;struct nl_cb *cb =NULL ;struct nl_msg *msg;int finished =0 ; +memset (alpha2,0 ,3 ); +struct nlattr *nl_reg_rules;const struct ieee80211_regdomain *rd =NULL ;
Signature · 1 line
1.8.4.rc3
PATCH v2 3/6 crda: add regulatory domain stream parser
In reply to Luis R. RodriguezThis adds a stream parser for regulatory domains. This allows developers to build regulatory domains now using the db.txt from a stream, either stdin, or a from an opened file.
This also adds a simple db2rd which for now only uses the library but with a bit of effort can also be used as a suitable replacement for the kernel's genregdb.awk.
--- Makefile | 10 +- db2rd.c | 32 ++++ reglib.c | 543 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ reglib.h | 44 ++++++ 4 files changed, 627 insertions(+), 2 deletions(-) create mode 100644 db2rd.c
Makefile +8 -2
@@ -24,10 +24,11 @@ PUBKEY_DIR?=pubkeys RUNTIME_PUBKEY_DIR?=/etc/wireless-regdb/pubkeys CFLAGS += -Wall -g +LDLIBS += -lm all: all_noverify verify -all_noverify: crda intersect regdbdump +all_noverify: crda intersect regdbdump db2rd ifeq ($(USE_OPENSSL),1) CFLAGS += -DUSE_OPENSSL -DPUBKEY_DIR=\"$(RUNTIME_PUBKEY_DIR)\" `pkg-config --cflags openssl`
@@ -121,6 +122,10 @@ intersect: reglib.o intersect.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) +db2rd: reglib.o db2rd.o + $(NQ) ' LD ' $@ + $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) + verify: $(REG_BIN) regdbdump $(NQ) ' CHK $(REG_BIN)' $(Q)./regdbdump $(REG_BIN) >/dev/null
@@ -152,5 +157,6 @@ install: crda crda.8.gz regdbdump.8.gz $(Q)$(INSTALL) -m 644 -t $(DESTDIR)/$(MANDIR)/man8/ regdbdump.8.gz clean: - $(Q)rm -f crda regdbdump intersect *.o *~ *.pyc keys-*.c *.gz \ + $(Q)rm -f crda regdbdump intersect db2rd \ + *.o *~ *.pyc keys-*.c *.gz \ udev/$(UDEV_LEVEL)regulatory.rules udev/regulatory.rules.parsed
db2rd.c new file +32 -0
@@ -0,0 +1,32 @@ +#include <errno.h> +#include <stdlib.h> +#include <stdio.h> +#include <arpa/inet.h> /* ntohl */ +#include <string.h> + +#include "nl80211.h" +#include "reglib.h" + +int main (int argc,char **argv) +{ +struct ieee80211_regdomain *rd =NULL ; +FILE *fp; + +if (argc !=1 ) { +fprintf (stderr,"Usage: cat db.txt | %s\n" , argv[0 ]); +return -EINVAL ; + } + + fp =reglib_create_parse_stream (stdin); +if (!fp) +return -EINVAL ; + +reglib_for_each_country_stream (fp, rd) { +reglib_print_regdom (rd); +free (rd); + } + +fclose (fp); + +return 0 ; +}
reglib.c +543 -0
552 lines not on this page · raw message
reglib.h +44 -0
64 lines not on this page · raw message
Signature · 1 line
1.8.4.rc3
PATCH v2 4/6 crda: add regulatory domain optimizer
In reply to Luis R. RodriguezThis adds a regulatory domain optimizer which can be used with information of a regulatory domain in db.txt format in stdin. It makes use of the new shiny regulatory domain stream parser.
The way this works is it iterates over the regulatory domain computing unions between each frequency, starting from each frequency as a pivot. If a union leads to a valid regulatory rule we verify that the pivot and othre frequency rules that provided that valid union can fit into that union regulatory rule by computing an intersection. If an intersection is possible it means two rules can be optimized out. We do this repetitively.
Note: cfg80211's nl80211.h API has:
#define NL80211_MAX_SUPP_REG_RULES 32
Our tools, both the stream parser and the optimizer are not limited to these artificial limits ! We can work on extending the kernel's limit but so far we have had no needs. A few notes below though on the existing reasoning for the limit and possible future enhancements.
This is used nl80211_set_reg() upon intercept of a regulatory domain being sent from userspace to it. We picked a limitation to at least have a stopping gap to avoid userpace flooding the kernel with a denial of service requests on memory from userspace. This means that userspace can only request at most a kmalloc of up to 32 regulatory rules for processing for the regulatory data that we are copying from userspace. There's a Linux kernel enhancement that will be made soon so that we invalidate bogus requests, by checking to see if the incomming regulatory domain alpha2 was not expected upon a regulatory hint initiator (even if userspace first tells the kernel it is waiting for a response from kernel space), and if its invalid then we drop the userspace supplied request, therefore avoiding some form of flooding on memory to the kernel.
Note that we can still get flooding if the userspace API is used to *request* to the kernel for a regulatory domain to be sent from userspace, in that case the kernel will properly expect the regulatory data for the alpha2. To prevent flooding there perhaps its a good idea for us to check whether a userspace pending request is pendingg and if so deny new updates until the last one triggers a timeout.
Screenshot for a US file with 40 rules:
mcgrof@frijol ~/devel/xlreg (git::master)$ cat us | grep --"(" | wc -l 40
mcgrof@frijol ~/devel/crda (git::master)$ cat us
country US: DFS-FCC
(2402.000 - 2422.000 @ 20.000), (30.00)
(2407.000 - 2427.000 @ 20.000), (30.00)
(2412.000 - 2432.000 @ 20.000), (30.00)
(2417.000 - 2437.000 @ 20.000), (30.00)
(2422.000 - 2442.000 @ 20.000), (30.00)
(2427.000 - 2447.000 @ 20.000), (30.00)
(2432.000 - 2452.000 @ 20.000), (30.00)
(2437.000 - 2457.000 @ 20.000), (30.00)
(2442.000 - 2462.000 @ 20.000), (30.00)
(2447.000 - 2467.000 @ 20.000), (30.00)
(2452.000 - 2472.000 @ 20.000), (30.00)
(2402.000 - 2442.000 @ 40.000), (30.00)
(2407.000 - 2447.000 @ 40.000), (30.00)
(2412.000 - 2452.000 @ 40.000), (30.00)
(2417.000 - 2457.000 @ 40.000), (30.00)
(2422.000 - 2462.000 @ 40.000), (30.00)
(2427.000 - 2467.000 @ 40.000), (30.00)
(2432.000 - 2472.000 @ 40.000), (30.00)
(5170.000 - 5190.000 @ 20.000), (17.00)
(5190.000 - 5210.000 @ 20.000), (17.00)
(5210.000 - 5230.000 @ 20.000), (17.00)
(5230.000 - 5250.000 @ 20.000), (17.00)
(5250.000 - 5270.000 @ 20.000), (23.00), DFS
(5270.000 - 5290.000 @ 20.000), (23.00), DFS
(5290.000 - 5310.000 @ 20.000), (23.00), DFS
(5310.000 - 5330.000 @ 20.000), (23.00), DFS
(5735.000 - 5755.000 @ 20.000), (30.00)
(5755.000 - 5775.000 @ 20.000), (30.00)
(5775.000 - 5795.000 @ 20.000), (30.00)
(5795.000 - 5815.000 @ 20.000), (30.00)
(5815.000 - 5835.000 @ 20.000), (30.00)
(5170.000 - 5210.000 @ 40.000), (17.00)
(5210.000 - 5250.000 @ 40.000), (17.00)
(5250.000 - 5290.000 @ 40.000), (23.00), DFS
(5290.000 - 5330.000 @ 40.000), (23.00), DFS
(5735.000 - 5775.000 @ 40.000), (30.00)
(5775.000 - 5815.000 @ 40.000), (30.00)
(5170.000 - 5250.000 @ 80.000), (17.00)
(5250.000 - 5330.000 @ 80.000), (23.00), DFS
(5735.000 - 5815.000 @ 80.000), (30.00)mcgrof@frijol ~/devel/crda (git::master)$ cat us | ./optimize country US: DFS-FCC
(2402.000 - 2472.000 @ 40.000), (30.00)
(5170.000 - 5250.000 @ 80.000), (17.00)
(5250.000 - 5330.000 @ 80.000), (23.00), DFS
(5735.000 - 5835.000 @ 80.000), (30.00)I've also tested this with the current db.txt from wireless-regdb and get real optimiziations which I will post later.
--- Makefile | 8 +- optimize.c | 40 +++++++++ reglib.c | 300 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- reglib.h | 16 ++++ 4 files changed, 360 insertions(+), 4 deletions(-) create mode 100644 optimize.c
Makefile +6 -2
@@ -28,7 +28,7 @@ LDLIBS += -lm all: all_noverify verify -all_noverify: crda intersect regdbdump db2rd +all_noverify: crda intersect regdbdump db2rd optimize ifeq ($(USE_OPENSSL),1) CFLAGS += -DUSE_OPENSSL -DPUBKEY_DIR=\"$(RUNTIME_PUBKEY_DIR)\" `pkg-config --cflags openssl`
@@ -126,6 +126,10 @@ db2rd: reglib.o db2rd.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) +optimize: reglib.o optimize.o + $(NQ) ' LD ' $@ + $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) + verify: $(REG_BIN) regdbdump $(NQ) ' CHK $(REG_BIN)' $(Q)./regdbdump $(REG_BIN) >/dev/null
@@ -157,6 +161,6 @@ install: crda crda.8.gz regdbdump.8.gz $(Q)$(INSTALL) -m 644 -t $(DESTDIR)/$(MANDIR)/man8/ regdbdump.8.gz clean: - $(Q)rm -f crda regdbdump intersect db2rd \ + $(Q)rm -f crda regdbdump intersect db2rd optimize \ *.o *~ *.pyc keys-*.c *.gz \ udev/$(UDEV_LEVEL)regulatory.rules udev/regulatory.rules.parsed
optimize.c new file +40 -0
@@ -0,0 +1,40 @@ +#include <errno.h> +#include <stdlib.h> +#include <stdio.h> +#include <arpa/inet.h> /* ntohl */ +#include <string.h> + +#include "nl80211.h" +#include "reglib.h" + +int main (int argc,char **argv) +{ +struct ieee80211_regdomain *rd =NULL , *rd_opt =NULL ; +FILE *fp; + +if (argc !=1 ) { +fprintf (stderr,"Usage: cat db.txt | %s\n" , argv[0 ]); +return -EINVAL ; + } + + fp =reglib_create_parse_stream (stdin); +if (!fp) +return -EINVAL ; + +reglib_for_each_country_stream (fp, rd) { + rd_opt =reglib_optimize_regdom (rd); +if (!rd_opt){ +fprintf (stderr,"Unable to optimize %c%c\n" , + rd->alpha2[0 ], + rd->alpha2[1 ]); +free (rd); +continue ; + } +reglib_print_regdom (rd_opt); +free (rd); +free (rd_opt); + } + +fclose (fp); +return 0 ; +}
reglib.c +298 -2
340 lines not on this page · raw message
reglib.h +16 -0
@@ -219,6 +219,22 @@ FILE *reglib_create_parse_stream(FILE *fp);*/ struct ieee80211_regdomain *reglib_parse_country (FILE *fp); +/** +* @reglib_optimize_regdom - optimize a regulatory domain +* +* @rd: a regulatory domain to be optimized +* +* A regulatory domain may exist without optimal expressions +* over its rules. This will look for regulatory rules that can +* be combined together to reduce the size of the regulatory +* domain and its expression. +* +* Regulatory rules will be combined if their max allowed +* bandwidth, max EIRP, and flags all match. +*/ +struct ieee80211_regdomain * +reglib_optimize_regdom (struct ieee80211_regdomain *rd); +#define reglib_for_each_country_stream (__fp, __rd) \ for (__rd = reglib_parse_country(__fp); \ __rd != NULL; \
Signature · 1 line
1.8.4.rc3
PATCH v2 5/6 crda: make ssl keys include stdint.h
In reply to Luis R. RodriguezThis is required to fix compilation if we
move reglig to its own library.
--- utils/key2pub.py | 2 ++ 1 file changed, 2 insertions(+)
utils/key2pub.py +2 -0
@@ -59,6 +59,7 @@ def print_ssl_32(output, name, val): def print_ssl(output, name, val): import struct + output.write('#include <stdint.h>\n') if len(struct.pack('@L', 0)) == 8: return print_ssl_64(output, name, val) else:
@@ -85,6 +86,7 @@ static struct pubkey keys[] = { pass def print_gcrypt(output, name, val): + output.write('#include <stdint.h>\n') while val[0] == '\0': val = val[1:] output.write('static const uint8_t %s[%d] = {\n' % (name, len(val)))
Signature · 1 line
1.8.4.rc3
PATCH v2 6/6 crda: make reglib a shared library
In reply to Luis R. RodriguezNow that we have quite a few helpers this puts the more valuable helpers into a library.
--- Makefile | 48 ++++++++++++++++++++++++++++++++++++------------ 1 file changed, 36 insertions(+), 12 deletions(-)
Makefile +36 -12
@@ -5,6 +5,8 @@ REG_GIT?=git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-regdb.g PREFIX ?= /usr/ MANDIR ?= $(PREFIX)/share/man/ +INCLUDE_DIR ?= $(PREFIX)/include/reglib/ +LIBDIR ?= $(PREFIX)/lib SBINDIR ?= /sbin/
@@ -23,24 +25,29 @@ UDEV_RULE_DIR?=/lib/udev/rules.d/ PUBKEY_DIR?=pubkeys RUNTIME_PUBKEY_DIR?=/etc/wireless-regdb/pubkeys +CFLAGS += -O2 -fpic +CFLAGS += -std=gnu99 -Wall -Werror -pedantic CFLAGS += -Wall -g LDLIBS += -lm +LDLIBREG += -lreg +LIBREG += libreg.so +LDFLAGS += -L ./ $(LDLIBREG) all: all_noverify verify -all_noverify: crda intersect regdbdump db2rd optimize +all_noverify: $(LIBREG) crda intersect regdbdump db2rd optimize ifeq ($(USE_OPENSSL),1) CFLAGS += -DUSE_OPENSSL -DPUBKEY_DIR=\"$(RUNTIME_PUBKEY_DIR)\" `pkg-config --cflags openssl` LDLIBS += `pkg-config --libs openssl` -reglib.o: keys-ssl.c +$(LIBREG): keys-ssl.c else CFLAGS += -DUSE_GCRYPT LDLIBS += -lgcrypt -reglib.o: keys-gcrypt.c +$(LIBREG): keys-gcrypt.c endif MKDIR ?= mkdir -p
@@ -106,39 +113,56 @@ keys-%.c: utils/key2pub.py $(wildcard $(PUBKEY_DIR)/*.pem) $(NQ) ' Trusted pubkeys:' $(wildcard $(PUBKEY_DIR)/*.pem) $(Q)./utils/key2pub.py --$* $(wildcard $(PUBKEY_DIR)/*.pem) $@ -%.o: %.c regdb.h reglib.h +$(LIBREG): regdb.h reglib.h reglib.c + $(NQ) ' CC ' $@ + $(Q)$(CC) $(CFLAGS) $(CPPFLAGS) -o $@ -shared -Wl,-soname,$(LIBREG) $^ + +install-libreg-headers: + $(NQ) ' INSTALL libreg-headers' + $(Q)mkdir -p $(INCLUDE_DIR) + $(Q)cp *.h $(INCLUDE_DIR)/ + +install-libreg: + $(NQ) ' INSTALL libreg' + $(Q)mkdir -p $(LIBDIR) + $(Q)cp $(LIBREG) $(LIBDIR)/ + $(Q)ldconfig + +%.o: %.c regdb.h $(LIBREG) $(NQ) ' CC ' $@ $(Q)$(CC) -c $(CPPFLAGS) $(CFLAGS) -o $@ $< -crda: reglib.o crda.o +crda: crda.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) $(NLLIBS) -regdbdump: reglib.o regdbdump.o +regdbdump: regdbdump.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) -intersect: reglib.o intersect.o +intersect: intersect.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) -db2rd: reglib.o db2rd.o +db2rd: db2rd.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) -optimize: reglib.o optimize.o +optimize: optimize.o $(NQ) ' LD ' $@ $(Q)$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $^ $(LDLIBS) verify: $(REG_BIN) regdbdump $(NQ) ' CHK $(REG_BIN)' - $(Q)./regdbdump $(REG_BIN) >/dev/null + $(Q)\ + LD_LIBRARY_PATH=.:$(LD_LIBRARY_PATH) \ + ./regdbdump $(REG_BIN) >/dev/null %.gz: % @$(NQ) ' GZIP' $< $(Q)gzip < $< > $@ -install: crda crda.8.gz regdbdump.8.gz +install: install-libreg install-libreg-headers crda crda.8.gz regdbdump.8.gz $(NQ) ' INSTALL crda' $(Q)$(MKDIR) $(DESTDIR)/$(SBINDIR) $(Q)$(INSTALL) -m 755 -t $(DESTDIR)/$(SBINDIR) crda
@@ -161,6 +185,6 @@ install: crda crda.8.gz regdbdump.8.gz $(Q)$(INSTALL) -m 644 -t $(DESTDIR)/$(MANDIR)/man8/ regdbdump.8.gz clean: - $(Q)rm -f crda regdbdump intersect db2rd optimize \ + $(Q)rm -f $(LIBREG) crda regdbdump intersect db2rd optimize \ *.o *~ *.pyc keys-*.c *.gz \ udev/$(UDEV_LEVEL)regulatory.rules udev/regulatory.rules.parsed
Signature · 1 line
1.8.4.rc3