aboutsummaryrefslogtreecommitdiffstats
path: root/src/vppinfra/rbtree.h
AgeCommit message (Collapse)AuthorFilesLines
2020-02-25svm: refactor fifoFlorin Coras1-0/+1
Type: refactor Switch from a wrapped byte space to a "continuous" one wherein fifo chunks are appended to the fifo as more data is enqueued and chunks are removed as data is dequeued. The fifo is still subject to a maximum size, i.e., maximum number of bytes that can be enqueued, so the max number of chunks associated to the fifo is also constrained. When enqueueing data, which must fit within the available free space, if not enough "supporting" chunk memory is available, the fifo asks the fifo segment for enough chunk memory to ensure that the write can succeed. To avoid allocating large amounts of small chunks due to small writes, if possible, the size of the chunks requested is lower capped by min_alloc. When dequeuing data, all the chunks that have been completely drained, i.e., head moved beyond the chunks’ end bytes, are unlinked from the fifo and returned to the fifo segment. The one exception to this is the last chunk which is never unlinked. Change-Id: I98c1dbd9135fb79650365c7e40c29238b96cd4ee Signed-off-by: Florin Coras <fcoras@cisco.com>
2020-02-25svm: refactor fifo chunk trackingFlorin Coras1-0/+1
Avoid tracking with rbtrees all of the chunks associated to a fifo. Instead, only track chunks when doing out-of-order operations (peek or ooo enqueue). Type: refactor Change-Id: I9f8bd266211746637d98e6a12ffc4b2d6346950a Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-06-18vppinfra: rbtree custom insert/search/delFlorin Coras1-0/+7
Type: feature Add support for insert/search/del with custom compare function. Change-Id: Ibb740afc224d8adc29d3e1b51b46cdd738d1bd93 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-24svm: fifo ooo reads/writes with multiple chunksFlorin Coras1-2/+20
Change-Id: If23a04623a7138c9f6c98ee9ecfa587396618a60 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-19rbtree: add successor and predecessor functionsFlorin Coras1-0/+2
Change-Id: I6934beaf5c08bae2d4f0bd3a6bb811810407c1f9 Signed-off-by: Florin Coras <fcoras@cisco.com>
2019-04-16vppinfra: add basic rbtreeFlorin Coras1-0/+84
Algorithm from CLRS, Introduction to Algorithms 3rd Edition, Ch. 13 Change-Id: I5bc2c507593770939cd5584f21dacf36ebd2b4c1 Signed-off-by: Florin Coras <fcoras@cisco.com>
r */ .highlight .p { color: #f8f8f2 } /* Punctuation */ .highlight .ch { color: #75715e } /* Comment.Hashbang */ .highlight .cm { color: #75715e } /* Comment.Multiline */ .highlight .cp { color: #75715e } /* Comment.Preproc */ .highlight .cpf { color: #75715e } /* Comment.PreprocFile */ .highlight .c1 { color: #75715e } /* Comment.Single */ .highlight .cs { color: #75715e } /* Comment.Special */ .highlight .gd { color: #f92672 } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .gi { color: #a6e22e } /* Generic.Inserted */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #75715e } /* Generic.Subheading */ .highlight .kc { color: #66d9ef } /* Keyword.Constant */ .highlight .kd { color: #66d9ef } /* Keyword.Declaration */ .highlight .kn { color: #f92672 } /* Keyword.Namespace */ .highlight .kp { color: #66d9ef } /* Keyword.Pseudo */ .highlight .kr { color: #66d9ef } /* Keyword.Reserved */ .highlight .kt { color: #66d9ef } /* Keyword.Type */ .highlight .ld { color: #e6db74 } /* Literal.Date */ .highlight .m { color: #ae81ff } /* Literal.Number */ .highlight .s { color: #e6db74 } /* Literal.String */ .highlight .na { color: #a6e22e } /* Name.Attribute */ .highlight .nb { color: #f8f8f2 } /* Name.Builtin */ .highlight .nc { color: #a6e22e } /* Name.Class */ .highlight .no { color: #66d9ef } /* Name.Constant */ .highlight .nd { color: #a6e22e } /* Name.Decorator */ .highlight .ni { color: #f8f8f2 } /* Name.Entity */ .highlight .ne { color: #a6e22e } /* Name.Exception */ .highlight .nf { color: #a6e22e } /* Name.Function */ .highlight .nl { color: #f8f8f2 } /* Name.Label */ .highlight .nn { color: #f8f8f2 } /* Name.Namespace */ .highlight .nx { color: #a6e22e } /* Name.Other */ .highlight .py { color: #f8f8f2 } /* Name.Property */ .highlight .nt { color: #f92672 } /* Name.Tag */ .highlight .nv { color: #f8f8f2 } /* Name.Variable */ .highlight .ow { color: #f92672 } /* Operator.Word */ .highlight .w { color: #f8f8f2 } /* Text.Whitespace */ .highlight .mb { color: #ae81ff } /* Literal.Number.Bin */ .highlight .mf { color: #ae81ff } /* Literal.Number.Float */ .highlight .mh { color: #ae81ff } /* Literal.Number.Hex */ .highlight .mi { color: #ae81ff } /* Literal.Number.Integer */ .highlight .mo { color: #ae81ff } /* Literal.Number.Oct */ .highlight .sa { color: #e6db74 } /* Literal.String.Affix */ .highlight .sb { color: #e6db74 } /* Literal.String.Backtick */ .highlight .sc { color: #e6db74 } /* Literal.String.Char */ .highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */ .highlight .sd { color: #e6db74 } /* Literal.String.Doc */ .highlight .s2 { color: #e6db74 } /* Literal.String.Double */ .highlight .se { color: #ae81ff } /* Literal.String.Escape */ .highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */ .highlight .si { color: #e6db74 } /* Literal.String.Interpol */ .highlight .sx { color: #e6db74 } /* Literal.String.Other */ .highlight .sr { color: #e6db74 } /* Literal.String.Regex */ .highlight .s1 { color: #e6db74 } /* Literal.String.Single */ .highlight .ss { color: #e6db74 } /* Literal.String.Symbol */ .highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #a6e22e } /* Name.Function.Magic */ .highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */ .highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */ .highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */ .highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */ .highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */ } @media (prefers-color-scheme: light) { .highlight .hll { background-color: #ffffcc } .highlight .c { color: #888888 } /* Comment */ .highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */ .highlight .k { color: #008800; font-weight: bold } /* Keyword */ .highlight .ch { color: #888888 } /* Comment.Hashbang */ .highlight .cm { color: #888888 } /* Comment.Multiline */ .highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */ .highlight .cpf { color: #888888 } /* Comment.PreprocFile */ .highlight .c1 { color: #888888 } /* Comment.Single */ .highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */ .highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ .highlight .ge { font-style: italic } /* Generic.Emph */ .highlight .gr { color: #aa0000 } /* Generic.Error */ .highlight .gh { color: #333333 } /* Generic.Heading */ .highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ .highlight .go { color: #888888 } /* Generic.Output */ .highlight .gp { color: #555555 } /* Generic.Prompt */ .highlight .gs { font-weight: bold } /* Generic.Strong */ .highlight .gu { color: #666666 } /* Generic.Subheading */ .highlight .gt { color: #aa0000 } /* Generic.Traceback */ .highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */ .highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */ .highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */ .highlight .kp { color: #008800 } /* Keyword.Pseudo */ .highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */ .highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */ .highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */ .highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */ .highlight .na { color: #336699 } /* Name.Attribute */ .highlight .nb { color: #003388 } /* Name.Builtin */ .highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */ .highlight .no { color: #003366; font-weight: bold } /* Name.Constant */ .highlight .nd { color: #555555 } /* Name.Decorator */ .highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */ .highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */ .highlight .nl { color: #336699; font-style: italic } /* Name.Label */ .highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */ .highlight .py { color: #336699; font-weight: bold } /* Name.Property */ .highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */ .highlight .nv { color: #336699 } /* Name.Variable */ .highlight .ow { color: #008800 } /* Operator.Word */ .highlight .w { color: #bbbbbb } /* Text.Whitespace */ .highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */ .highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */ .highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */ .highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */ .highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */ .highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */ .highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */ .highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */ .highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */ .highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */ .highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */ .highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */ .highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */ .highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */ .highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */ .highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */ .highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */ .highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */ .highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */ .highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */ .highlight .vc { color: #336699 } /* Name.Variable.Class */ .highlight .vg { color: #dd7700 } /* Name.Variable.Global */ .highlight .vi { color: #3333bb } /* Name.Variable.Instance */ .highlight .vm { color: #336699 } /* Name.Variable.Magic */ .highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */ }
#!/usr/bin/env python3

import unittest
from framework import VppTestCase, VppTestRunner
from util import ppp
from scapy.packet import Raw
from scapy.layers.inet import IP, UDP
from syslog_rfc5424_parser import SyslogMessage, ParseError
from syslog_rfc5424_parser.constants import SyslogFacility, SyslogSeverity
from vpp_papi import VppEnum


class TestSyslog(VppTestCase):
    """ Syslog Protocol Test Cases """

    @property
    def SYSLOG_SEVERITY(self):
        return VppEnum.vl_api_syslog_severity_t

    @classmethod
    def setUpClass(cls):
        super(TestSyslog, cls).setUpClass()

        try:
            cls.pg0, = cls.create_pg_interfaces(range(1))
            cls.pg0.admin_up()
            cls.pg0.config_ip4()
            cls.pg0.resolve_arp()

        except Exception:
            super(TestSyslog, cls).tearDownClass()
            raise

    @classmethod
    def tearDownClass(cls):
        super(TestSyslog, cls).tearDownClass()

    def syslog_generate(self, facility, severity, appname, msgid, sd=None,
                        msg=None):
        """
        Generate syslog message

        :param facility: facility value
        :param severity: severity level
        :param appname: application name that originate message
        :param msgid: message identifier
        :param sd: structured data (optional)
        :param msg: free-form message (optional)
        """
        facility_str = ['kernel', 'user-level', 'mail-system',
                        'system-daemons', 'security-authorization', 'syslogd',
                        'line-printer', 'network-news', 'uucp', 'clock-daemon',
                        '', 'ftp-daemon', 'ntp-subsystem', 'log-audit',
                        'log-alert', '', 'local0', 'local1', 'local2',
                        'local3', 'local4', 'local5', 'local6', 'local7']

        severity_str = ['emergency', 'alert', 'critical', 'error', 'warning',
                        'notice', 'informational', 'debug']

        cli_str = "test syslog %s %s %s %s" % (facility_str[facility],
                                               severity_str[severity],
                                               appname,
                                               msgid)
        if sd is not None:
            for sd_id, sd_params in sd.items():
                cli_str += " sd-id %s" % (sd_id)
                for name, value in sd_params.items():
                    cli_str += " sd-param %s %s" % (name, value)
        if msg is not None:
            cli_str += " %s" % (msg)
        self.vapi.cli(cli_str)

    def syslog_verify(self, data, facility, severity, appname, msgid, sd=None,
                      msg=None):
        """
        Verify syslog message

        :param data: syslog message
        :param facility: facility value
        :param severity: severity level
        :param appname: application name that originate message
        :param msgid: message identifier
        :param sd: structured data (optional)
        :param msg: free-form message (optional)
        """
        message = data.decode('utf-8')
        if sd is None:
            sd = {}
        try:
            message = SyslogMessage.parse(message)
        except ParseError as e:
            self.logger.error(e)
            raise
        else:
            self.assertEqual(message.facility, facility)
            self.assertEqual(message.severity, severity)
            self.assertEqual(message.appname, appname)
            self.assertEqual(message.msgid, msgid)
            self.assertEqual(message.msg, msg)
            self.assertEqual(message.sd, sd)
            self.assertEqual(message.version, 1)
            self.assertEqual(message.hostname, self.pg0.local_ip4)

    def test_syslog(self):
        """ Syslog Protocol test """
        self.vapi.syslog_set_sender(src_address=self.pg0.local_ip4,
                                    collector_address=self.pg0.remote_ip4)
        config = self.vapi.syslog_get_sender()
        self.assertEqual(str(config.collector_address),
                         self.pg0.remote_ip4)
        self.assertEqual(config.collector_port, 514)
        self.assertEqual(str(config.src_address), self.pg0.local_ip4)
        self.assertEqual(config.vrf_id, 0)
        self.assertEqual(config.max_msg_size, 480)

        appname = 'test'
        msgid = 'testMsg'
        msg = 'this is message'
        sd1 = {'exampleSDID@32473': {'iut': '3',
                                     'eventSource': 'App',
                                     'eventID': '1011'}}
        sd2 = {'exampleSDID@32473': {'iut': '3',
                                     'eventSource': 'App',
                                     'eventID': '1011'},
               'examplePriority@32473': {'class': 'high'}}

        self.pg_enable_capture(self.pg_interfaces)
        self.syslog_generate(SyslogFacility.local7,
                             SyslogSeverity.info,
                             appname,
                             msgid,
                             None,
                             msg)
        capture = self.pg0.get_capture(1)
        try:
            self.assertEqual(capture[0][IP].src, self.pg0.local_ip4)
            self.assertEqual(capture[0][IP].dst, self.pg0.remote_ip4)
            self.assertEqual(capture[0][UDP].dport, 514)
            self.assert_packet_checksums_valid(capture[0], False)
        except:
            self.logger.error(ppp("invalid packet:", capture[0]))
            raise
        self.syslog_verify(capture[0][Raw].load,
                           SyslogFacility.local7,
                           SyslogSeverity.info,
                           appname,
                           msgid,
                           None,
                           msg)

        self.pg_enable_capture(self.pg_interfaces)
        self.vapi.syslog_set_filter(
            self.SYSLOG_SEVERITY.SYSLOG_API_SEVERITY_WARN)
        filter = self.vapi.syslog_get_filter()
        self.assertEqual(filter.severity,
                         self.SYSLOG_SEVERITY.SYSLOG_API_SEVERITY_WARN)
        self.syslog_generate(SyslogFacility.local7,
                             SyslogSeverity.info,
                             appname,
                             msgid,
                             None,
                             msg)
        self.pg0.assert_nothing_captured()

        self.pg_enable_capture(self.pg_interfaces)
        self.syslog_generate(SyslogFacility.local6,
                             SyslogSeverity.warning,
                             appname,
                             msgid,
                             sd1,
                             msg)
        capture = self.pg0.get_capture(1)
        self.syslog_verify(capture[0][Raw].load,
                           SyslogFacility.local6,
                           SyslogSeverity.warning,
                           appname,
                           msgid,
                           sd1,
                           msg)

        self.vapi.syslog_set_sender(self.pg0.local_ip4,
                                    self.pg0.remote_ip4,
                                    collector_port=12345)
        config = self.vapi.syslog_get_sender()
        self.assertEqual(config.collector_port, 12345)

        self.pg_enable_capture(self.pg_interfaces)
        self.syslog_generate(SyslogFacility.local5,
                             SyslogSeverity.err,
                             appname,
                             msgid,
                             sd2,
                             None)
        capture = self.pg0.get_capture(1)
        try:
            self.assertEqual(capture[0][UDP].dport, 12345)
        except:
            self.logger.error(ppp("invalid packet:", capture[0]))
            raise
        self.syslog_verify(capture[0][Raw].load,
                           SyslogFacility.local5,
                           SyslogSeverity.err,
                           appname,
                           msgid,
                           sd2,
                           None)


if __name__ == '__main__':
    unittest.main(testRunner=VppTestRunner)