aboutsummaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAge
* [LIB]: Knuth-Morris-Pratt textsearch algorithmThomas Graf2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | 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 theory Signed-off-by: Thomas Graf <tgraf@suug.ch> Signed-off-by: David S. Miller <davem@davemloft.net>
* [LIB]: Textsearch infrastructure.Thomas Graf2005-06-23
| | | | | | | | | | 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 <tgraf@suug.ch> Signed-off-by: David S. Miller <davem@davemloft.net>
* [TCP]: Allow choosing TCP congestion control via sockopt.Stephen Hemminger2005-06-23
| | | | | | | | Allow using setsockopt to set TCP congestion control to use on a per socket basis. Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NET]: Separate two usages of netdev_max_backlog.Stephen Hemminger2005-06-23
| | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NET]: Eliminate netif_rx massive packet drops.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NET]: Remove obsolete netif_rx congestion sensing mechanism.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NET]: Remove obsolete fastroute stats.Stephen Hemminger2005-06-23
| | | | | | | Remove last vestiages of fastroute code that is no longer used. Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* Merge rsync://rsync.kernel.org/pub/scm/linux/kernel/git/aegl/linux-2.6Linus Torvalds2005-06-23
|\
| * [IA64] Fix pfn_to_nid() so the kernel compiles again for !CONFIG_DISCONTIGMEM.David Mosberger-Tang2005-06-23
| | | | | | | | | | Signed-off-by: David Mosberger-Tang <davidm@hpl.hp.com> Signed-off-by: Tony Luck <tony.luck@intel.com>
* | Merge rsync://rsync.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6Linus Torvalds2005-06-23
|\ \
| * | [TCP]: Add Scalable TCP congestion control module.John Heffner2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <jheffner@psc.edu> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add H-TCP congestion control module.Baruch Even2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <baruch@ev-en.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add TCP Vegas congestion control module.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add TCP Hybla congestion control module.Daniele Lacamera2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add High Speed TCP congestion control module.John Heffner2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | Sally Floyd's high speed TCP congestion control. This is useful for comparison and research. Signed-off-by: John Heffner <jheffner@psc.edu> Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add TCP Westwood congestion control module.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add TCP BIC congestion control module.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Update sysctl and congestion control documentation.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Report congestion control algorithm in tcp_diag.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Change tcp_diag to use the existing __RTA_PUT() macro.Stephen Hemminger2005-06-23
| | | | | | | | | | | | | | | Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
| * | [TCP]: Add pluggable congestion control algorithm infrastructure.Stephen Hemminger2005-06-23
| |/ | | | | | | | | | | | | | | | | | | 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 <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* | Merge master.kernel.org:/home/rmk/linux-2.6-armLinus Torvalds2005-06-23
|\ \
| * | [PATCH] ARM: 2730/1: S3C2410 default configuration updateBen Dooks2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Patch from Ben Dooks Add support for the DM9000 and bring default configuration up-to-date with the latest 2.6.12 kernel release Signed-off-by: Ben Dooks <ben-linux@fluff.org> Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
| * | [PATCH] ARM: 2729/1: DM9000 platform support for S3C2410 machines (BAST, VR1000)Ben Dooks2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <ben-linux@fluff.org> Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
| * | [PATCH] ARM: 2728/1: S3C2410 - fix constant warning on serial device nameBen Dooks2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | Patch from Ben Dooks Remove warning of casting `const char *` to a `char *` type. Signed-off-by: Ben Dooks <ben-linux@fluff.org> Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
| * | [PATCH] ARM: 2722/1: remove reliance on udivdi3 for nwfpeNicolas Pitre2005-06-23
| | | | | | | | | | | | | | | | | | | | | Patch from Nicolas Pitre Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
| * | [PATCH] ARM: 2721/1: remove reliance on udivdi3 for pxafb driverNicolas Pitre2005-06-23
| | | | | | | | | | | | | | | | | | | | | Patch from Nicolas Pitre Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
* | | Merge master.kernel.org:/home/rmk/linux-2.6-serialLinus Torvalds2005-06-23
|\ \ \ | |_|/ |/| |
| * | [PATCH] Serial: Bugs are not capabilitiesRussell King2005-06-23
| | | | | | | | | | | | Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
| * | [PATCH] Serial: Mobility's 16550A ports need a helping handRussell King2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | The Mobility 16550A serial ports don't behave the same as standard 16550A ports, and need a helping hand to get them going once the transmitter has drained and been disabled. Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
| * | [PATCH] Serial: Convert 8250 revision-based bug fixes to bug bitmaskRussell King2005-06-23
| |/ | | | | | | | | | | | | | | | | For some 8250 port types, we used to check the type of the port, and then determine whether the chip revision means the device is buggy. Instead, introduce a bit array, and set the appropriate bit(s) when we discover a buggy device. Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
* | [PATCH] Add removal schedule of register_serial/unregister_serial to ↵Russell King2005-06-23
| | | | | | | | appropriate file
* | [PATCH] better USB_MON dependenciesAdrian Bunk2005-06-23
| | | | | | | | | | | | | | This makes the USB_MON less confusing. Signed-off-by: Adrian Bunk <bunk@stusta.de> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | Merge rsync://rsync.kernel.org/pub/scm/linux/kernel/git/paulus/ppc64-2.6Linus Torvalds2005-06-23
|\ \
| * | [PATCH] Maple powerdown patchDavid Gibson2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Currently reset and powerdown are not implemented on the Maple board, and attempting to do so will (incorrectly return). This implements the proper communication with the service processor, allowing correct reset and powerdown on the Maple board, by communicating with the service processor. If somehow it's unable to communicate with the service processor it will loop forever instead. Note that powerdown on the Maple will power down the CPUs, but not the fans or other board components due to hardware and firmware limitations. Signed-off-by: David Gibson <dwg@au1.ibm.com> Signed-off-by: Frank Rowand <frowand@mvista.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] pSeries - read irqs dynamicallyJohn Rose2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | For I/O DLPAR to work properly, the kernel needs to allow for dynamic assignment of the irq field of the pci_dev structure upon dynamic bus addition. This patch moves the assignment of that field from pSeries_final_fixup() to pcibios_fixup_bus(), which enables dynamic assignment for the children of a newly added bus. Currently, pci_devs receive their irq numbers in one of two ways. The irq line is either read at boot for all pci_devs, or read by the rpaphp module at slot enable time. The latter is no longer sufficient for DLPAR addition of slots that don't qualify as PCI-hotplug capable. This solution handles the cases of boot and dynamic add. Signed-off-by: John Rose <johnrose@austin.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] correct printing to operator panelMike Strosaker2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch corrects the printing of progress indicators to the op panel on p/iSeries ppc64 systems. Each discrete reference code should begin with a form feed char to clear the op panel, and the first and second lines should be separated with a CR/LF sequence. Padding with spaces is not necessary. Also, capitalize the hex value printed on the first line, to be consistent with the values printed by firmware, service processor, etc. It turns out that there's an ibm,form-feed property; this patch uses it in the pSeries-specific progress routine. This patch also checks the number of rows and the specific width of each row (the second row on power5 systems can actually hold 80 characters). If the displayed text is too wide for the physical display, it can be viewed in the ASM menus, or by selecting option 14 on the op panel. Signed-off-by: Mike Strosaker <strosake@austin.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: Add driver for BPA iommuArnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Implementation of software load support for the BE iommu. This is very different from other iommu code on ppc64, since we only do a static mapping. The mapping is currently hardcoded but should really be read from the firmware, but they don't set up the device nodes yet. There is a single 512MB DMA window for PCI, USB and ethernet at 0x20000000 for our RAM. The Cell processor can put the I/O page table either in memory like the hashed page table (hardware load) or have the operating system write the entries into memory mapped CPU registers (software load). I use the software load mechanism because I know that all I/O page table entries for the amount of installed physical memory fit into the IO TLB cache. At the point when we get machines with more than 4GB of installed memory, we can either use hardware I/O page table access like the other platforms do or dynamically update the I/O TLB entries when a page fault occurs in the I/O subsystem. The software load can then use the macros that I have implemented for the static mapping in order to do the TLB cache updates. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: Add driver for BPA interrupt controllersArnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Add support for the integrated interrupt controller on BPA CPUs. There is one of those for each SMT thread. The mapping of interrupt numbers to HW interrupt sources is described in arch/ppc64/kernel/bpa_iic.h. This version hardcodes the 'Spider' chip as the secondary interrupt controller. That is not really generic for the architecture, but at the moment it is the only secondary PIC that exists. A little more work will be needed on this as soon as we have boards with multiple external interrupt controllers. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: add BPA platform typeArnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This adds the basic support for running on BPA machines. So far, this is only the IBM workstation, and it will not run on others without a little more generalization. It should be possible to configure a kernel for any combination of CONFIG_PPC_BPA with any of the other multiplatform targets. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: add a watchdog driver for rtasUtz Bacher2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Add a watchdog using the RTAS OS surveillance service. This is provided as a simpler alternative to rtasd. The added value is that it works with standard watchdog client programs and can therefore also do user space monitoring. On BPA, rtasd is not really useful because the hardware does not have much to report with event-scan. The driver should also work on other platforms that support the OS surveillance rtas calls. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: add a minimal nvram driverUtz Bacher2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The firmware provides the location and size of the nvram in the device tree, so it does not really contain any hardware specific bits and could be used on other machines as well. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: pSeries_progress -> rtas_progressArnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The pSeries_progress function is called from some places in the rtas code, which may also be used by non-pSeries platforms. Though pSeries is currently the only platform type that implements display-character, the code is actually generic enough to be part of the rtas subsystem. I hit a bug here because the generic rtas code tried calling ppc_md.progress, which points to an __init function on most platforms. We could also clear the ppc_md.progress pointer when freeing the init memory to make it more explicit that ppc_md.progress must not be called after bootup. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: Split out generic rtas code from pSeries_pci.c.Arnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | BPA is using rtas for PCI but should not be confused by pSeries code. This also avoids some #ifdefs. Other platforms that want to use rtas_pci.c could create their own platform_pci.c with platform specific fixups. Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: rename pSeries rtc functions into rtas_*Arnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | The rtc rtas functions are not pSeries specific but can also be used by BPA and other SLOF based platforms Signed-off-by: Arnd Bergmann <arndb@de.ibm.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
| * | [PATCH] ppc64: consolidate calibrate_decr implementationsArnd Bergmann2005-06-22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | pSeries and maple have almost the same code for calibrate_decr, and BPA would need yet another copy. Instead, I'm moving the code to arch/ppc64/kernel/time.c. Some of the related declarations were missing from header files, so I'm moving those as well. It makes sense to merge this with the pmac function of the same name, so we end up having just one implemetation for iSeries and one for Open Firmware based machines. Signed-off-by: Arnd Bergmann <arnd@arndb.de> Signed-off-by: Paul Mackerras <paulus@samba.org>
* | | [PATCH] sys_open() cleanupTelemaque Ndizihiwe2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | Clean up tortured logic in sys_open(). Signed-off-by: Telemaque Ndizihiwe <telendiz@eircom.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | | [PATCH] Convert users to tty_unregister_ldisc()Alexey Dobriyan2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | tty_register_ldisc(N_FOO, NULL) => tty_unregister_ldisc(N_FOO) Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | | [PATCH] Introduce tty_unregister_ldisc()Alexey Dobriyan2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | It's a bit strange to see tty_register_ldisc call in modules' exit functions. Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | | [PATCH] pwc-uncompress warning fixAndrew Morton2005-06-23
| | | | | | | | | | | | | | | | | | | | | | | | 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 statement Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-19 05:58:30 -0500