/* * lib/ts_kmp.c Knuth-Morris-Pratt text search implementation * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version * 2 of the License, or (at your option) any later version. * * Authors: Thomas Graf * * ========================================================================== * * 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 */ #include #include #include #include #include struct ts_kmp { u8 * pattern; unsigned int pattern_len; unsigned int prefix_tbl[0]; }; static unsigned int kmp_find(struct ts_config *conf, struct ts_state *state) { struct ts_kmp *kmp = ts_config_priv(conf); unsigned int i, q = 0, text_len, consumed = state->offset; const u8 *text; const int icase = conf->flags & TS_IGNORECASE; for (;;) { text_len = conf->get_next_block(consumed, &text, conf, state); if (unlikely(text_len == 0)) break; for (i = 0; i < text_len; i++) { while (q > 0 && kmp->pattern[q] != (icase ? toupper(text[i]) : text[i])) q = kmp->prefix_tbl[q - 1]; if (kmp->pattern[q] == (icase ? toupper(text[i]) : text[i])) q++; if (unlikely(q == kmp->pattern_len)) { state->offset = consumed + i + 1; return state->offset - kmp->pattern_len; } } consumed += text_len; } return UINT_MAX; } static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len, unsigned int *prefix_tbl, int flags) { unsigned int k, q; const u8 icase = flags & TS_IGNORECASE; for (k = 0, q = 1; q < len; q++) { while (k > 0 && (icase ? toupper(pattern[k]) : pattern[k]) != (icase ? toupper(pattern[q]) : pattern[q])) k = prefix_tbl[k-1]; if ((icase ? toupper(pattern[k]) : pattern[k]) == (icase ? toupper(pattern[q]) : pattern[q])) k++; prefix_tbl[q] = k; } } static struct ts_config *kmp_init(const void *pattern, unsigned int len, gfp_t gfp_mask, int flags) { struct ts_config *conf; struct ts_kmp *kmp; int i; unsigned int prefix_tbl_len = len * sizeof(unsigned int); size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len; conf = alloc_ts_config(priv_size, gfp_mask); if (IS_ERR(conf)) return conf; conf->flags = flags; kmp = ts_config_priv(conf); kmp->pattern_len = len; compute_prefix_tbl(pattern, len, kmp->prefix_tbl, flags); kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len; if (flags & TS_IGNORECASE) for (i = 0; i < len; i++) kmp->pattern[i] = toupper(((u8 *)pattern)[i]); else memcpy(kmp->pattern, pattern, len); return conf; } static void *kmp_get_pattern(struct ts_config *conf) { struct ts_kmp *kmp = ts_config_priv(conf); return kmp->pattern; } static unsigned int kmp_get_pattern_len(struct ts_config *conf) { struct ts_kmp *kmp = ts_config_priv(conf); return kmp->pattern_len; } static struct ts_ops kmp_ops = { .name = "kmp", .find = kmp_find, .init = kmp_init, .get_pattern = kmp_get_pattern, .get_pattern_len = kmp_get_pattern_len, .owner = THIS_MODULE, .list = LIST_HEAD_INIT(kmp_ops.list) }; static int __init init_kmp(void) { return textsearch_register(&kmp_ops); } static void __exit exit_kmp(void) { textsearch_unregister(&kmp_ops); } MODULE_LICENSE("GPL"); module_init(init_kmp); module_exit(exit_kmp); t;2017-01-27 08:11:44 -0800 committerDavid S. Miller <davem@davemloft.net>2017-01-29 18:30:56 -0500 commitf1712c73714088a7252d276a57126d56c7d37e64 (patch) tree962ee49daf8d1cba8403fcf03b315d4a142ec944 /tools/testing parentdc97a89e726c4e1830320d1db8215ef77ecebae0 (diff)
can: Fix kernel panic at security_sock_rcv_skb
Zhang Yanmin reported crashes [1] and provided a patch adding a synchronize_rcu() call in can_rx_unregister() The main problem seems that the sockets themselves are not RCU protected. If CAN uses RCU for delivery, then sockets should be freed only after one RCU grace period. Recent kernels could use sock_set_flag(sk, SOCK_RCU_FREE), but let's ease stable backports with the following fix instead. [1] BUG: unable to handle kernel NULL pointer dereference at (null) IP: [<ffffffff81495e25>] selinux_socket_sock_rcv_skb+0x65/0x2a0 Call Trace: <IRQ> [<ffffffff81485d8c>] security_sock_rcv_skb+0x4c/0x60 [<ffffffff81d55771>] sk_filter+0x41/0x210 [<ffffffff81d12913>] sock_queue_rcv_skb+0x53/0x3a0 [<ffffffff81f0a2b3>] raw_rcv+0x2a3/0x3c0 [<ffffffff81f06eab>] can_rcv_filter+0x12b/0x370 [<ffffffff81f07af9>] can_receive+0xd9/0x120 [<ffffffff81f07beb>] can_rcv+0xab/0x100 [<ffffffff81d362ac>] __netif_receive_skb_core+0xd8c/0x11f0 [<ffffffff81d36734>] __netif_receive_skb+0x24/0xb0 [<ffffffff81d37f67>] process_backlog+0x127/0x280 [<ffffffff81d36f7b>] net_rx_action+0x33b/0x4f0 [<ffffffff810c88d4>] __do_softirq+0x184/0x440 [<ffffffff81f9e86c>] do_softirq_own_stack+0x1c/0x30 <EOI> [<ffffffff810c76fb>] do_softirq.part.18+0x3b/0x40 [<ffffffff810c8bed>] do_softirq+0x1d/0x20 [<ffffffff81d30085>] netif_rx_ni+0xe5/0x110 [<ffffffff8199cc87>] slcan_receive_buf+0x507/0x520 [<ffffffff8167ef7c>] flush_to_ldisc+0x21c/0x230 [<ffffffff810e3baf>] process_one_work+0x24f/0x670 [<ffffffff810e44ed>] worker_thread+0x9d/0x6f0 [<ffffffff810e4450>] ? rescuer_thread+0x480/0x480 [<ffffffff810ebafc>] kthread+0x12c/0x150 [<ffffffff81f9ccef>] ret_from_fork+0x3f/0x70 Reported-by: Zhang Yanmin <yanmin.zhang@intel.com> Signed-off-by: Eric Dumazet <edumazet@google.com> Acked-by: Oliver Hartkopp <socketcan@hartkopp.net> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'tools/testing')