Oops, sorry, I didn't realize that my patches was rather big (75K). I didn't
compress them. I guess that's why my mail hasn't been delivered yet. However
here it is again. You can download it at:
http://www.dtek.chalmers.se/~d97gozem/hashslot_superlimit.tar.bz2 (16K)
Thank you!
----- Forwarded message from gozem -----
Subject: [PATCH] superlimit (and hashslot)
Date: Wed, 10 Apr 2002 02:21:20 +0200
To: [EMAIL PROTECTED]
User-Agent: Mutt/1.3.28i
I have now finished my superlimit. Its a new version of limit with the same
purpose but far more features. This is two patches: superlimit and hashslot.
Hashslot is not a match, target nor conntrack helper. Its just a data
structure, hash-table with slots in one memory chunk. Its is used by
superlimit and upcoming ippool. Recent and psd should be rewritten using it.
As recent only uses one large linked list (last time I check, I might be
wrong here) and psd only uses a static hash-table using a roundrobin
algorithm for replacing slots. A carefully selected attack can get it to
overwrite each slot in a "perfect" order. I'll just paste the help no how it
works from the .h file below.
superlimit changes one smal thing in iptables.c (userspace). iptables.c
isn't exporting mask_to_dotted() which is clearly needed in superlimit when
parsing command line. I changed that, one line in iptables.c and one line in
iptables.h
This one can limit on both packets and bytes. More flexable syntax. You can
now limit to 3/2sec (1,5 / sec). It uses 64bits counters and a new algorithm
which is faster and more accurate. And best of all, you can limit on per net
pairs. If one host or net is flooding you it will automaticlly only limit
that host or net, all after your own settings. Not having impact on the
other normal traffic passing.
I have seen discussion about that we shouldn't have bytes limits since
traffic shaping should do that. I belive its requested very highly of users
and its not that many more lines of code in my solution. I have not tested
if this really works good to shape traffic. Its not a good way but its
works. Should probaly not be used for shaping but rather for pure limiting.
Apply the hashslot patch first.
Please send me comments and bugreports.
I'm, also pasting the iptables -m superlimit --help to show how it works.
-----8<------
superlimit v0.1.0 options:
--slimit-packets avg Max average match for packet rate.
--slimit-bytes avg Max average match for byte rate.
--slimit-start num Number to match in a burst, default the same as avg.
Must be more than avg. The starting condition is an
absolut value and not a multiplier for avg.
--slimit-srcmask num Mask to group source address on. Bits or mask.
Defaults is to not use per net limit.
--slimit-dstmask num Mask to group destination address on. Bits or mask.
Default is to not use per net limit.
--slimit-wholepacket In bytes limit, calcute the the entire packet size,
not only the IP-packet size.
--slimit-maxslots num The max number of slots to hold data for
sourcenet,destnet pairs. Each slot uses 24 bytes
of memory. Default is to use max 4 pages of
memory,
thats 680 slot.You can also specify the number of
pages you want to use, eg. num=5pages.
The algorithm uses one page of memory to start
with
and increases, decreases as nessesary.
--slimit-outmem-match If we run out of slots, instead of not matching the
packet, match it.
Both --slimit-packets and --slimit-bytes have the following syntax:
number[unit]/[number][timeunit], where
unit can be K (times 1000), M (times 10^6), G (times 10^9), T (times 10^12).
timeunit can be second (s), minute (m), hour (h), day (d), default second
Example: 4/second 7/d 6K/h 5M/3sec
Examples:
-m superlimit --slimit-packets 2/s --slimit-start 4
Match only 2 packets per second, but only do that after going
above 4 packets per second.
-m superlimit --slimit-bytes ! 10K/s --slimit-wholepacket
Match 10Kilobytes (10000 bytes) per second. Count the wire size of
the packet.
-m superlimit --slimit-packets ! 5/3sec --slimit-start 10
Match every packet ABOVE 5 packets per 3 second. Starting at 10 packets
per 3 second.
-m superlimit --slimit-packets 3K/5min --slimit-srcmask 24
Match 3000 packets per 5min form each /24 subnet. Great if you get
flooded from host(s) at X.Y.Z.*, but don't want to limit the rest of
the world.
-m superlimit --slimit-packets 1/s --slimit-srcmask 32 \
--slimit-maxslots 1024
Limit all the hosts on internet, but don't use more than 1024 source-dest
pairs of memory for this so a flood can't eat up all our memory.
-m superlimit --slimit-bytes 2G/day --slimit-dstmask 32 \
--slimit-maxslots 16pages --slimit-outmem-match
Limit all the hosts we are routing for to 5GigaByte per day, don't use
more than 16 pages of memory. If we are out of memory let the packet pass.
-m superlimit --slimit-packets 1/sec --slimit-start 50 \
--slimit-srcmask 24 --slimit-dstmask 32
Limit (eg. SYN and/or PING floods) so that internet can't flood per
computer behind us that we are routing for.
-------8<-----
-----8<------
Description of hashslot:
This is a container structure. It uses one memory chunk in order to keep the
use of malloc() and free() down. It splits this memory chunk into slots.
Each slot of the same size can be used to what ever purpose you like. It
also handles a hashtable in order to be able to lookup a slot fast.
It supports garabage collection in order to free up slots. This freature can
be disabled.
It supports rehashing in order to keep the memory usage down when alot of
slots are free, and to increase the number of available slots when running
out of free slots. This freature can also be disabled.
All operations are O(1) except hashslot_foreach() and
hashslot_garbagecollect() which visits each used slot once.
The structure keeps track of the free slots by linking them up in a list. It
does not link up every slot in this queue on startup. It instead keeps an
index (hash->inited) of which slots havn't even been used once. Therefor is
the number of freeslots always: (slots_number - inited) + freecount
You can change any of the parameters during use but these: hashtable,
hashtable_number, slots, slots_number first_free, last_free, freecount
Who should use this?
Anyone that wants a fast cointainer for thier objects. When disabling the
garbage collection it wont give you any more overhead but one compare in
each function. Same goes for rehashing, but only affects hashslot_newslot
and hashslot_delslot.
This code and be both be used as a module in the kernel or as a library in
any userspace program. Both is supported.
-------8<---
--
/Gozem A.K.A. Joakim Axelsson
