• Luis R. Rodriguez's avatar
    crda: add regulatory domain optimizer · 0b8105a9
    Luis R. Rodriguez authored
    This 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.
    Signed-off-by: 's avatarLuis R. Rodriguez <mcgrof@do-not-panic.com>
    0b8105a9