prosody
783056b4e448
util/queue.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Annotate

util/queue.lua @ 12181:783056b4e448 0.11 0.11.12

util.xml: Do not allow doctypes, comments or processing instructions Yes. This is as bad as it sounds. CVE pending. In Prosody itself, this only affects mod_websocket, which uses util.xml to parse the <open/> frame, thus allowing unauthenticated remote DoS using Billion Laughs. However, third-party modules using util.xml may also be affected by this. This commit installs handlers which disallow the use of doctype declarations and processing instructions without any escape hatch. It, by default, also introduces such a handler for comments, however, there is a way to enable comments nontheless. This is because util.xml is used to parse human-facing data, where comments are generally a desirable feature, and also because comments are generally harmless.
author Jonas Schäfer <jonas@wielicki.name>
date Mon, 10 Jan 2022 18:23:54 +0100
parent 11103:73b8aaf55775
child 11114:6a608ecb3471
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
1 -- Prosody IM
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
2 -- Copyright (C) 2008-2015 Matthew Wild
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
3 -- Copyright (C) 2008-2015 Waqas Hussain
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
4 --
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
5 -- This project is MIT/X11 licensed. Please see the
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
6 -- COPYING file in the source package for more information.
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
7 --
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
8
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
9 -- Small ringbuffer library (i.e. an efficient FIFO queue with a size limit)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
10 -- (because unbounded dynamically-growing queues are a bad thing...)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
11
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
12 local have_utable, utable = pcall(require, "util.table"); -- For pre-allocation of table
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
13
6731
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
14 local function new(size, allow_wrapping)
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
15 -- Head is next insert, tail is next read
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
16 local head, tail = 1, 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
17 local items = 0; -- Number of stored items
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
18 local t = have_utable and utable.create(size, 0) or {}; -- Table to hold items
6912
cb5b14c95b7b util.queue: Add luacheck annotations
Matthew Wild <mwild1@gmail.com>
parents: 6911
diff changeset
19 --luacheck: ignore 212/self
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
20 return {
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
21 _items = t;
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
22 size = size;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
23 count = function (self) return items; end;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
24 push = function (self, item)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
25 if items >= size then
6731
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
26 if allow_wrapping then
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
27 tail = (tail%size)+1; -- Advance to next oldest item
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
28 items = items - 1;
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
29 else
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
30 return nil, "queue full";
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
31 end
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
32 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
33 t[head] = item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
34 items = items + 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
35 head = (head%size)+1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
36 return true;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
37 end;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
38 pop = function (self)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
39 if items == 0 then
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
40 return nil;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
41 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
42 local item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
43 item, t[tail] = t[tail], 0;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
44 tail = (tail%size)+1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
45 items = items - 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
46 return item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
47 end;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
48 peek = function (self)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
49 if items == 0 then
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
50 return nil;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
51 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
52 return t[tail];
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
53 end;
11103
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
54 replace = function (self, data)
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
55 if items == 0 then
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
56 return self:push(data);
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
57 end
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
58 t[tail] = data;
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
59 return true;
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
60 end;
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
61 items = function (self)
6912
cb5b14c95b7b util.queue: Add luacheck annotations
Matthew Wild <mwild1@gmail.com>
parents: 6911
diff changeset
62 --luacheck: ignore 431/t
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
63 return function (t, pos)
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
64 if pos >= t:count() then
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
65 return nil;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
66 end
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
67 local read_pos = tail + pos;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
68 if read_pos > t.size then
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
69 read_pos = (read_pos%size);
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
70 end
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
71 return pos+1, t._items[read_pos];
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
72 end, self, 0;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
73 end;
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
74 };
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
75 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
76
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
77 return {
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
78 new = new;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
79 };
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
80