24 Jun, 2005
40 commits
-
Signed-off-by: Thomas Graf
Signed-off-by: David S. Miller -
Finds a pattern in the skb data according to the specified
textsearch configuration. Use textsearch_next() to retrieve
subsequent occurrences of the pattern. Returns the offset
to the first occurrence or UINT_MAX if no match was found.Signed-off-by: Thomas Graf
Signed-off-by: David S. Miller -
Implements sequential reading for both linear and non-linear
skb data at zerocopy cost. The data is returned in chunks of
arbitary length, therefore random access is not possible.Usage:
from := 0
to := 128
state := undef
data := undef
len := undef
consumed := 0skb_prepare_seq_read(skb, from, to, &state)
while (len = skb_seq_read(consumed, &data, &state)) != 0 do
/* do something with 'data' of length 'len' */
if abort then
/* abort read if we don't wait for
* skb_seq_read() to return 0 */
skb_abort_seq_read(&state)
return
endif
/* not necessary to consume all of 'len' */
consumed += len
doneSigned-off-by: Thomas Graf
Signed-off-by: David S. Miller -
A finite state machine consists of n states (struct ts_fsm_token)
representing the pattern as a finite automation. The data is read
sequentially on a octet basis. Every state token specifies the number
of recurrences and the type of value accepted which can be either a
specific character or ctype based set of characters. The available
type of recurrences include 1, (0|1), [0 n], and [1 n].The algorithm differs between strict/non-strict mode specyfing
whether the pattern has to start at the first octect. Strict mode
is enabled by default and can be disabled by inserting
TS_FSM_HEAD_IGNORE as the first token in the chain.The runtime performance of the algorithm should be around O(n),
however while in strict mode the average runtime can be better.Signed-off-by: Thomas Graf
Signed-off-by: David S. Miller -
Implements a linear-time string-matching algorithm due to Knuth,
Morris, and Pratt [1]. Their algorithm avoids the explicit
computation of the transition function DELTA altogether. Its
matching time is O(n), for n being length(text), using just an
auxiliary function PI[1..m], for m being length(pattern),
precomputed from the pattern in time O(m). The array PI allows
the transition function DELTA to be computed efficiently
"on the fly" as needed. Roughly speaking, for any state
"q" = 0,1,...,m and any character "a" in SIGMA, the value
PI["q"] contains the information that is independent of "a" and
is needed to compute DELTA("q", "a") [2]. Since the array PI
has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
save a factor of |SIGMA| in the preprocessing time by computing
PI rather than DELTA.[1] Cormen, Leiserson, Rivest, Stein
Introdcution to Algorithms, 2nd Edition, MIT Press
[2] See finite automation theorySigned-off-by: Thomas Graf
Signed-off-by: David S. Miller -
The textsearch infrastructure provides text searching
facitilies for both linear and non-linear data.
Individual search algorithms are implemented in modules
and chosen by the user.Signed-off-by: Thomas Graf
Signed-off-by: David S. Miller -
Allow using setsockopt to set TCP congestion control to use on a per
socket basis.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Separate out the two uses of netdev_max_backlog. One controls the
upper bound on packets processed per softirq, the new name for this is
netdev_budget; the other controls the limit on packets queued via
netif_rx.Increase the max_backlog default to account for faster processors.
Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Eliminate the throttling behaviour when the netif receive queue fills
because it behaves badly when using high speed networks under load.
The throttling cause multiple packet drops that cause TCP to go into
slow start mode. The same effective patch has been part of BIC TCP and
H-TCP as well as part of Web100.The existing code drops 100's of packets when the queue fills;
this changes it to individual packet drop-tail.Signed-off-by: Stephen Hemmminger
Signed-off-by: David S. Miller -
Remove the congestion sensing mechanism from netif_rx, and always
return either full or empty. Almost no driver checks the return value
from netif_rx, and those that do only use it for debug messages.The original design of netif_rx was to do flow control based on the
receive queue, but NAPI has supplanted this and no driver uses the
feedback.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Remove last vestiages of fastroute code that is no longer used.
Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Signed-off-by: David Mosberger-Tang
Signed-off-by: Tony Luck -
Signed-off-by: Russell King
-
Patch from Ben Dooks
Add support for the DM9000 and bring default configuration
up-to-date with the latest 2.6.12 kernel releaseSigned-off-by: Ben Dooks
Signed-off-by: Russell King -
Patch from Ben Dooks
Add platform_device information for DM9000 chip(s) on the
Simtec BAST and the VR1000 board.Signed-off-by: Ben Dooks
Signed-off-by: Russell King -
Patch from Ben Dooks
Remove warning of casting `const char *` to a `char *` type.
Signed-off-by: Ben Dooks
Signed-off-by: Russell King -
Patch from Nicolas Pitre
Signed-off-by: Nicolas Pitre
Signed-off-by: Russell King -
Patch from Nicolas Pitre
Signed-off-by: Nicolas Pitre
Signed-off-by: Russell King -
This patch implements Tom Kelly's Scalable TCP congestion control algorithm
for the modular framework.The algorithm has some nice scaling properties, and has been used a fair bit
in research, though is known to have significant fairness issues, so it's not
really suitable for general purpose use.Signed-off-by: John Heffner
Signed-off-by: David S. Miller -
H-TCP is a congestion control algorithm developed at the Hamilton Institute, by
Douglas Leith and Robert Shorten. It is extending the standard Reno algorithm
with mode switching is thus a relatively simple modification.H-TCP is defined in a layered manner as it is still a research platform. The
basic form includes the modification of beta according to the ratio of maxRTT
to min RTT and the alpha=2*factor*(1-beta) relation, where factor is dependant
on the time since last congestion.The other layers improve convergence by adding appropriate factors to alpha.
The following patch implements the H-TCP algorithm in it's basic form.
Signed-Off-By: Baruch Even
Signed-off-by: David S. Miller -
TCP Vegas code modified for the new TCP infrastructure.
Vegas now uses microsecond resolution timestamps for
better estimation of performance over higher speed links.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
TCP Hybla congestion avoidance.
- "In heterogeneous networks, TCP connections that incorporate a
terrestrial or satellite radio link are greatly disadvantaged with
respect to entirely wired connections, because of their longer round
trip times (RTTs). To cope with this problem, a new TCP proposal, the
TCP Hybla, is presented and discussed in the paper[1]. It stems from an
analytical evaluation of the congestion window dynamics in the TCP
standard versions (Tahoe, Reno, NewReno), which suggests the necessary
modifications to remove the performance dependence on RTT.[...]"[1][1]: Carlo Caini, Rosario Firrincieli, "TCP Hybla: a TCP enhancement for
heterogeneous networks",
International Journal of Satellite Communications and Networking
Volume 22, Issue 5 , Pages 547 - 566. September 2004.Signed-off-by: Daniele Lacamera (root at danielinux.net)net
Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Sally Floyd's high speed TCP congestion control.
This is useful for comparison and research.Signed-off-by: John Heffner
Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
This is the existing 2.6.12 Westwood code moved from tcp_input
to the new congestion framework. A lot of the inline functions
have been eliminated to try and make it clearer.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
TCP BIC congestion control reworked to use the new congestion control
infrastructure. This version is more up to date than the BIC
code in 2.6.12; it incorporates enhancements from BICTCP 1.1,
to handle low latency links.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Update the documentation to remove the old sysctl values and
include the new congestion control infrastructure. Includes
changes to tcp.txt by Ian McDonald.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Enhancement to the tcp_diag interface used by the iproute2 ss command
to report the tcp congestion control being used by a socket.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
Allow TCP to have multiple pluggable congestion control algorithms.
Algorithms are defined by a set of operations and can be built in
or modules. The legacy "new RENO" algorithm is used as a starting
point and fallback.Signed-off-by: Stephen Hemminger
Signed-off-by: David S. Miller -
This makes the USB_MON less confusing.
Signed-off-by: Adrian Bunk
Signed-off-by: Linus Torvalds -
Clean up tortured logic in sys_open().
Signed-off-by: Telemaque Ndizihiwe
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
tty_register_ldisc(N_FOO, NULL) => tty_unregister_ldisc(N_FOO)
Signed-off-by: Alexey Dobriyan
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
It's a bit strange to see tty_register_ldisc call in modules' exit
functions.Signed-off-by: Alexey Dobriyan
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
drivers/usb/media/pwc/pwc-uncompress.c: In function `pwc_decompress':
drivers/usb/media/pwc/pwc-uncompress.c:140: warning: unreachable code at beginning of switch statementSigned-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
