)]}' { "log": [ { "commit": "65df877ab2e2328a4704af218efaed0a45176c86", "tree": "ec7cf77ddc08fca3c007dc0ac209d1e7ba2953d3", "parents": [ "a8acfbac75c2ffdd66fb5dfcdb7ab5aaced94fd8" ], "author": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Thu Jun 23 23:49:52 2005 -0700" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Thu Jun 23 23:49:52 2005 -0700" }, "message": "[LIB]: textsearch.o needs to be obj-y not lib-y.\n\nIt exports symbols.\n\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n" }, { "commit": "6408f79cce401e1bfecf923e7156f84f96e021e3", "tree": "203624ffacf60d364293adc47d2f59f6ba81dd35", "parents": [ "df3fb93ad9ec0b20c785c0ad82d42d159a1af272" ], "author": { "name": "Thomas Graf", "email": "tgraf@suug.ch", "time": "Thu Jun 23 20:59:16 2005 -0700" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Thu Jun 23 20:59:16 2005 -0700" }, "message": "[LIB]: Naive finite state machine based textsearch\n\nA finite state machine consists of n states (struct ts_fsm_token)\nrepresenting the pattern as a finite automation. The data is read\nsequentially on a octet basis. Every state token specifies the number\nof recurrences and the type of value accepted which can be either a\nspecific character or ctype based set of characters. The available\ntype of recurrences include 1, (0|1), [0 n], and [1 n].\n\nThe algorithm differs between strict/non-strict mode specyfing\nwhether the pattern has to start at the first octect. Strict mode\nis enabled by default and can be disabled by inserting\nTS_FSM_HEAD_IGNORE as the first token in the chain.\n\nThe runtime performance of the algorithm should be around O(n),\nhowever while in strict mode the average runtime can be better.\n\nSigned-off-by: Thomas Graf \u003ctgraf@suug.ch\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n" }, { "commit": "df3fb93ad9ec0b20c785c0ad82d42d159a1af272", "tree": "e29ba25f55cb77e24310999a949b433e98d7656e", "parents": [ "2de4ff7bd658c97fb357efa3095a509674dacb5a" ], "author": { "name": "Thomas Graf", "email": "tgraf@suug.ch", "time": "Thu Jun 23 20:58:37 2005 -0700" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Thu Jun 23 20:58:37 2005 -0700" }, "message": "[LIB]: Knuth-Morris-Pratt textsearch algorithm\n\nImplements a linear-time string-matching algorithm due to Knuth,\nMorris, and Pratt [1]. Their algorithm avoids the explicit\ncomputation of the transition function DELTA altogether. Its\nmatching time is O(n), for n being length(text), using just an\nauxiliary function PI[1..m], for m being length(pattern),\nprecomputed from the pattern in time O(m). The array PI allows\nthe transition function DELTA to be computed efficiently\n\"on the fly\" as needed. Roughly speaking, for any state\n\"q\" \u003d 0,1,...,m and any character \"a\" in SIGMA, the value\nPI[\"q\"] contains the information that is independent of \"a\" and\nis needed to compute DELTA(\"q\", \"a\") [2]. Since the array PI\nhas only m entries, whereas DELTA has O(m|SIGMA|) entries, we\nsave a factor of |SIGMA| in the preprocessing time by computing\nPI rather than DELTA.\n \n[1] Cormen, Leiserson, Rivest, Stein\n Introdcution to Algorithms, 2nd Edition, MIT Press\n[2] See finite automation theory\n\nSigned-off-by: Thomas Graf \u003ctgraf@suug.ch\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n" }, { "commit": "2de4ff7bd658c97fb357efa3095a509674dacb5a", "tree": "49036dbf594317a6a17ff4e56f65158a6aeacbda", "parents": [ "5f8ef48d240963093451bcf83df89f1a1364f51d" ], "author": { "name": "Thomas Graf", "email": "tgraf@suug.ch", "time": "Thu Jun 23 20:49:30 2005 -0700" }, "committer": { "name": "David S. Miller", "email": "davem@davemloft.net", "time": "Thu Jun 23 20:49:30 2005 -0700" }, "message": "[LIB]: Textsearch infrastructure.\n\nThe textsearch infrastructure provides text searching\nfacitilies for both linear and non-linear data.\nIndividual search algorithms are implemented in modules\nand chosen by the user.\n\nSigned-off-by: Thomas Graf \u003ctgraf@suug.ch\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n" }, { "commit": "f14f75b81187cdbe10cc53a521bf9fdf97b59f8c", "tree": "5c0d48c8a3338e6f1747e6cd55f699be96ffef1a", "parents": [ "2caaad41e4aa8f5dd999695b4ddeaa0e7f3912a4" ], "author": { "name": "Jes Sorensen", "email": "jes@wildopensource.com", "time": "Tue Jun 21 17:15:02 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@ppc970.osdl.org", "time": "Tue Jun 21 18:46:18 2005 -0700" }, "message": "[PATCH] ia64 uncached alloc\n\nThis patch contains the ia64 uncached page allocator and the generic\nallocator (genalloc). The uncached allocator was formerly part of the SN2\nmspec driver but there are several other users of it so it has been split\noff from the driver.\n\nThe generic allocator can be used by device driver to manage special memory\netc. The generic allocator is based on the allocator from the sym53c8xx_2\ndriver.\n\nVarious users on ia64 needs uncached memory. The SGI SN architecture requires\nit for inter-partition communication between partitions within a large NUMA\ncluster. The specific user for this is the XPC code. Another application is\nlarge MPI style applications which use it for synchronization, on SN this can\nbe done using special \u0027fetchop\u0027 operations but it also benefits non SN\nhardware which may use regular uncached memory for this purpose. Performance\nof doing this through uncached vs cached memory is pretty substantial. This\nis handled by the mspec driver which I will push out in a seperate patch.\n\nRather than creating a specific allocator for just uncached memory I came up\nwith genalloc which is a generic purpose allocator that can be used by device\ndrivers and other subsystems as they please. For instance to handle onboard\ndevice memory. It was derived from the sym53c7xx_2 driver\u0027s allocator which\nis also an example of a potential user (I am refraining from modifying sym2\nright now as it seems to have been under fairly heavy development recently).\n\nOn ia64 memory has various properties within a granule, ie. it isn\u0027t safe to\naccess memory as uncached within the same granule as currently has memory\naccessed in cached mode. The regular system therefore doesn\u0027t utilize memory\nin the lower granules which is mixed in with device PAL code etc. The\nuncached driver walks the EFI memmap and pulls out the spill uncached pages\nand sticks them into the uncached pool. Only after these chunks have been\nutilized, will it start converting regular cached memory into uncached memory.\nHence the reason for the EFI related code additions.\n\nSigned-off-by: Jes Sorensen \u003cjes@wildopensource.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "39c715b71740c4a78ba4769fb54826929bac03cb", "tree": "94dd679dfc8e6c2db65971739aa8c8c6206f8174", "parents": [ "84929801e14d968caeb84795bfbb88f04283fbd9" ], "author": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Tue Jun 21 17:14:34 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@ppc970.osdl.org", "time": "Tue Jun 21 18:46:13 2005 -0700" }, "message": "[PATCH] smp_processor_id() cleanup\n\nThis patch implements a number of smp_processor_id() cleanup ideas that\nArjan van de Ven and I came up with.\n\nThe previous __smp_processor_id/_smp_processor_id/smp_processor_id API\nspaghetti was hard to follow both on the implementational and on the\nusage side.\n\nSome of the complexity arose from picking wrong names, some of the\ncomplexity comes from the fact that not all architectures defined\n__smp_processor_id.\n\nIn the new code, there are two externally visible symbols:\n\n - smp_processor_id(): debug variant.\n\n - raw_smp_processor_id(): nondebug variant. Replaces all existing\n uses of _smp_processor_id() and __smp_processor_id(). Defined\n by every SMP architecture in include/asm-*/smp.h.\n\nThere is one new internal symbol, dependent on DEBUG_PREEMPT:\n\n - debug_smp_processor_id(): internal debug variant, mapped to\n smp_processor_id().\n\nAlso, i moved debug_smp_processor_id() from lib/kernel_lock.c into a new\nlib/smp_processor_id.c file. All related comments got updated and/or\nclarified.\n\nI have build/boot tested the following 8 .config combinations on x86:\n\n {SMP,UP} x {PREEMPT,!PREEMPT} x {DEBUG_PREEMPT,!DEBUG_PREEMPT}\n\nI have also build/boot tested x64 on UP/PREEMPT/DEBUG_PREEMPT. (Other\narchitectures are untested, but should work just fine.)\n\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\nSigned-off-by: Arjan van de Ven \u003carjan@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@osdl.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@osdl.org\u003e\n" }, { "commit": "9a19fea43616066561e221359596ce532e631395", "tree": "f776bee1bcb1051bf75323b65fa887347412409e", "parents": [ "6034a080f98b0bbc0a058e2ac65a538f75cffeee" ], "author": { "name": "mochel@digitalimplant.org", "email": "mochel@digitalimplant.org", "time": "Mon Mar 21 11:45:16 2005 -0800" }, "committer": { "name": "Greg Kroah-Hartman", "email": "gregkh@suse.de", "time": "Mon Jun 20 15:15:14 2005 -0700" }, "message": "[PATCH] Add initial implementation of klist helpers.\n\nThis klist interface provides a couple of structures that wrap around\nstruct list_head to provide explicit list \"head\" (struct klist) and\nlist \"node\" (struct klist_node) objects. For struct klist, a spinlock\nis included that protects access to the actual list itself. struct\nklist_node provides a pointer to the klist that owns it and a kref\nreference count that indicates the number of current users of that node\nin the list.\n\nThe entire point is to provide an interface for iterating over a list\nthat is safe and allows for modification of the list during the\niteration (e.g. insertion and removal), including modification of the\ncurrent node on the list.\n\nIt works using a 3rd object type - struct klist_iter - that is declared\nand initialized before an iteration. klist_next() is used to acquire the\nnext element in the list. It returns NULL if there are no more items.\nThis klist interface provides a couple of structures that wrap around\nstruct list_head to provide explicit list \"head\" (struct klist) and\nlist \"node\" (struct klist_node) objects. For struct klist, a spinlock\nis included that protects access to the actual list itself. struct\nklist_node provides a pointer to the klist that owns it and a kref\nreference count that indicates the number of current users of that node\nin the list.\n\nThe entire point is to provide an interface for iterating over a list\nthat is safe and allows for modification of the list during the\niteration (e.g. insertion and removal), including modification of the\ncurrent node on the list.\n\nIt works using a 3rd object type - struct klist_iter - that is declared\nand initialized before an iteration. klist_next() is used to acquire the\nnext element in the list. It returns NULL if there are no more items.\nInternally, that routine takes the klist\u0027s lock, decrements the reference\ncount of the previous klist_node and increments the count of the next\nklist_node. It then drops the lock and returns.\n\nThere are primitives for adding and removing nodes to/from a klist.\nWhen deleting, klist_del() will simply decrement the reference count.\nOnly when the count goes to 0 is the node removed from the list.\nklist_remove() will try to delete the node from the list and block\nuntil it is actually removed. This is useful for objects (like devices)\nthat have been removed from the system and must be freed (but must wait\nuntil all accessors have finished).\n\nInternally, that routine takes the klist\u0027s lock, decrements the reference\ncount of the previous klist_node and increments the count of the next\nklist_node. It then drops the lock and returns.\n\nThere are primitives for adding and removing nodes to/from a klist.\nWhen deleting, klist_del() will simply decrement the reference count.\nOnly when the count goes to 0 is the node removed from the list.\nklist_remove() will try to delete the node from the list and block\nuntil it is actually removed. This is useful for objects (like devices)\nthat have been removed from the system and must be freed (but must wait\nuntil all accessors have finished).\n\nSigned-off-by: Patrick Mochel \u003cmochel@digitalimplant.org\u003e\nSigned-off-by: Greg Kroah-Hartman \u003cgregkh@suse.de\u003e\n\ndiff -Nru a/include/linux/klist.h b/include/linux/klist.h\n" }, { "commit": "1da177e4c3f41524e886b7f1b8a0c1fc7321cac2", "tree": "0bba044c4ce775e45a88a51686b5d9f90697ea9d", "parents": [], "author": { "name": "Linus Torvalds", "email": "torvalds@ppc970.osdl.org", "time": "Sat Apr 16 15:20:36 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@ppc970.osdl.org", "time": "Sat Apr 16 15:20:36 2005 -0700" }, "message": "Linux-2.6.12-rc2\n\nInitial git repository build. I\u0027m not bothering with the full history,\neven though we have it. We can create a separate \"historical\" git\narchive of that later if we want to, and in the meantime it\u0027s about\n3.2GB when imported into git - space that would just make the early\ngit days unnecessarily complicated, when we don\u0027t have a lot of good\ninfrastructure for it.\n\nLet it rip!\n" } ] }