From nobody Thu Jul 07 05:20:35 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id C87E11CFF520; Thu, 7 Jul 2022 05:20:36 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Ldl9c02xdz3Hw7; Thu, 7 Jul 2022 05:20:35 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657171236; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=b7K0Zz/9aB7pZNaBYU1A5zOweVrQwZVpaVlMMTj3x+c=; b=NjI8nLWEJReUOSXKG9SUMTab1mKiCTlwMf4zHBwyZKbS0qOI/pRcJBIjt99SxnqZaZxcnq 9I8Kc58t7xmVsQKJ9YE8nS1PJIaQKdffXx7kF963VvjJ23xM4Iub06eEQQCm+lPTkxeUyF DMtbI4kZaDcxIH/a9vUNZk9F2Q6Tm5uPW7iNiDqrtT5M67qnRiFwZClBlZZTLu/CZTJoEd LrzFPuk/s1Iqg7sij0gzdjvQFkp0ibqyD/FmMDKBiruMlHhxWi7ZkD/hQd6QpAW333iPA+ n/zdCRRuvde1tKdcXLyF4ZlzCw4bXVLy2i0yeG1SsR2XMmmavIVj/QRP2yWfIg== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4Ldl9b4jkGzWsQ; Thu, 7 Jul 2022 05:20:35 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 2675KZ5U081629; Thu, 7 Jul 2022 05:20:35 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 2675KZjO081628; Thu, 7 Jul 2022 05:20:35 GMT (envelope-from git) Date: Thu, 7 Jul 2022 05:20:35 GMT Message-Id: <202207070520.2675KZjO081628@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Gleb Smirnoff Subject: git: a83d596f434f - main - sockstat(1): use tree(3) rbtree instead of hash List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: glebius X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: a83d596f434f5f8ec771ad6b207a0d3e5252680d Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657171236; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=b7K0Zz/9aB7pZNaBYU1A5zOweVrQwZVpaVlMMTj3x+c=; b=lfrqLbyDXQVza+WvbALFYhf8gNyxUA/sLbaRyrSfyFbtO+uDZ15cSLzdDuyj5h8qtwhUag 8nGxynC05UJ5tjFISWm9tNuqM5q2xsnCUB8MOWzFCJ3JCeViiA4JB2LIYx/aO+XOyhVd5z 7tq+C5edIBwKjX80DsNReT5oVtrEsmcDyf18d0zLEljaDKEpfzttipe8fQjxVD/ATSktRi qAJPjq1gBqvLcH3GAPGVFt1UTlhrDFIvziODStWdgVIXrg3/vvn5W57zIAjjopLA86FTob DuEe11dN3tGnwOrW8bnBrsfiw0ZROgfYU5htZ1XhMlL23+b14AJHVsmjYgz3jA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1657171236; a=rsa-sha256; cv=none; b=K/Umgvj29GCP7TH3wLdK2AzPY8YTZsuvMYuNjiXdGCMDrKbt6KmnBgSwpGgQUceo5+Wwhd A/ks0DVC6U/H3KHNhRyBmRyreXnMsYKktn2YR2yttd6DPZbw9XJWk+f76D3RHp8SvrKjy5 QTKVftDZYESvBnyP0NDdXUaOV9pL+nsGnFrDxb40wS6t5Xu+4Z9tXbEHhXIf4QliY2Fcuo 5s5Iq+JuBTVbO34Y/1t8zYPEfsETatksZs34tOVq7S+GDPIH/cae2P5GqMsp7JSfO3C4Z4 tMpjyrkUCPegegewnG92Mdk7J+MidfKLtT3ITKqObcxsGM02AkOyFAzYh1JJjQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by glebius: URL: https://cgit.FreeBSD.org/src/commit/?id=a83d596f434f5f8ec771ad6b207a0d3e5252680d commit a83d596f434f5f8ec771ad6b207a0d3e5252680d Author: Gleb Smirnoff AuthorDate: 2022-07-07 05:19:08 +0000 Commit: Gleb Smirnoff CommitDate: 2022-07-07 05:19:08 +0000 sockstat(1): use tree(3) rbtree instead of hash o Use tree to lookup by socket kvaddr. The size of hash is too big for a small virtual machine and at the same time too little for a large production server. A tree would better fit here. o For those pcbs, that don't have a socket associated, use a list. o Provide a second tree to lookup by pcb kvaddr. These removes full hash traversal when printing every unix(4) socket. Reviewed by: tuexen Differential revision: https://reviews.freebsd.org/D35724 --- usr.bin/sockstat/sockstat.c | 105 ++++++++++++++++++++++++-------------------- 1 file changed, 57 insertions(+), 48 deletions(-) diff --git a/usr.bin/sockstat/sockstat.c b/usr.bin/sockstat/sockstat.c index a4cba95ab983..7f9286b95f92 100644 --- a/usr.bin/sockstat/sockstat.c +++ b/usr.bin/sockstat/sockstat.c @@ -38,6 +38,8 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include +#include #include #include @@ -119,6 +121,11 @@ struct addr { }; struct sock { + union { + RB_ENTRY(sock) socket_tree; /* tree of pcbs with socket */ + SLIST_ENTRY(sock) socket_list; /* list of pcbs w/o socket */ + }; + RB_ENTRY(sock) pcb_tree; kvaddr_t socket; kvaddr_t pcb; uint64_t inp_gencnt; @@ -132,11 +139,25 @@ struct sock { char cc[TCP_CA_NAME_MAX]; struct addr *laddr; struct addr *faddr; - struct sock *next; }; -#define HASHSIZE 1009 -static struct sock *sockhash[HASHSIZE]; +static RB_HEAD(socks_t, sock) socks = RB_INITIALIZER(&socks); +static int64_t +socket_compare(const struct sock *a, const struct sock *b) +{ + return ((int64_t)(a->socket/2 - b->socket/2)); +} +RB_GENERATE_STATIC(socks_t, sock, socket_tree, socket_compare); + +static RB_HEAD(pcbs_t, sock) pcbs = RB_INITIALIZER(&pcbs); +static int64_t +pcb_compare(const struct sock *a, const struct sock *b) +{ + return ((int64_t)(a->pcb/2 - b->pcb/2)); +} +RB_GENERATE_STATIC(pcbs_t, sock, pcb_tree, pcb_compare); + +static SLIST_HEAD(, sock) nosocks = SLIST_HEAD_INITIALIZER(&nosocks); static struct xfile *xfiles; static int nxfiles; @@ -350,7 +371,7 @@ gather_sctp(void) const char *varname; size_t len, offset; char *buf; - int hash, vflag; + int vflag; int no_stcb, local_all_loopback, foreign_all_loopback; vflag = 0; @@ -469,10 +490,7 @@ gather_sctp(void) (!opt_L || !local_all_loopback) && ((xinpcb->flags & SCTP_PCB_FLAGS_UDPTYPE) || (xstcb->last == 1))) { - hash = (int)((uintptr_t)sock->socket % - HASHSIZE); - sock->next = sockhash[hash]; - sockhash[hash] = sock; + RB_INSERT(socks_t, &socks, sock); } else { free_socket(sock); } @@ -597,10 +615,7 @@ gather_sctp(void) (!opt_L || !(local_all_loopback || foreign_all_loopback))) { - hash = (int)((uintptr_t)sock->socket % - HASHSIZE); - sock->next = sockhash[hash]; - sockhash[hash] = sock; + RB_INSERT(socks_t, &socks, sock); } else { free_socket(sock); } @@ -624,7 +639,7 @@ gather_inet(int proto) const char *varname, *protoname; size_t len, bufsize; void *buf; - int hash, retry, vflag; + int retry, vflag; vflag = 0; if (opt_4) @@ -760,9 +775,10 @@ gather_inet(int proto) memcpy(sock->cc, xtp->xt_cc, TCP_CA_NAME_MAX); } sock->protoname = protoname; - hash = (int)((uintptr_t)sock->socket % HASHSIZE); - sock->next = sockhash[hash]; - sockhash[hash] = sock; + if (sock->socket != 0) + RB_INSERT(socks_t, &socks, sock); + else + SLIST_INSERT_HEAD(&nosocks, sock, socket_list); } out: free(buf); @@ -778,7 +794,7 @@ gather_unix(int proto) const char *varname, *protoname; size_t len, bufsize; void *buf; - int hash, retry; + int retry; switch (proto) { case SOCK_STREAM: @@ -852,9 +868,8 @@ gather_unix(int proto) faddr->next = NULL; sock->laddr = laddr; sock->faddr = faddr; - hash = (int)((uintptr_t)sock->socket % HASHSIZE); - sock->next = sockhash[hash]; - sockhash[hash] = sock; + RB_INSERT(socks_t, &socks, sock); + RB_INSERT(pcbs_t, &pcbs, sock); } out: free(buf); @@ -1052,7 +1067,7 @@ static void displaysock(struct sock *s, int pos) { kvaddr_t p; - int hash, first, offset; + int first, offset; struct addr *laddr, *faddr; struct sock *s_tmp; @@ -1104,15 +1119,8 @@ displaysock(struct sock *s, int pos) break; } pos += xprintf("-> "); - for (hash = 0; hash < HASHSIZE; ++hash) { - for (s_tmp = sockhash[hash]; - s_tmp != NULL; - s_tmp = s_tmp->next) - if (s_tmp->pcb == p) - break; - if (s_tmp != NULL) - break; - } + s_tmp = RB_FIND(pcbs_t, &pcbs, + &(struct sock){ .pcb = p }); if (s_tmp == NULL || s_tmp->laddr == NULL || s_tmp->laddr->address.ss_len == 0) pos += xprintf("??"); @@ -1222,7 +1230,7 @@ display(void) struct passwd *pwd; struct xfile *xf; struct sock *s; - int hash, n, pos; + int n, pos; if (opt_q != 1) { printf("%-8s %-10s %-5s %-2s %-6s %-*s %-*s", @@ -1250,12 +1258,9 @@ display(void) continue; if (opt_j >= 0 && opt_j != getprocjid(xf->xf_pid)) continue; - hash = (int)((uintptr_t)xf->xf_data % HASHSIZE); - for (s = sockhash[hash]; s != NULL; s = s->next) { - if (s->socket != xf->xf_data) - continue; - if (!check_ports(s)) - continue; + s = RB_FIND(socks_t, &socks, + &(struct sock){ .socket = xf->xf_data}); + if (s != NULL && check_ports(s)) { s->shown = 1; pos = 0; if (opt_n || @@ -1277,17 +1282,21 @@ display(void) } if (opt_j >= 0) return; - for (hash = 0; hash < HASHSIZE; hash++) { - for (s = sockhash[hash]; s != NULL; s = s->next) { - if (s->shown) - continue; - if (!check_ports(s)) - continue; - pos = 0; - pos += xprintf("%-8s %-10s %-5s %-2s ", - "?", "?", "?", "?"); - displaysock(s, pos); - } + SLIST_FOREACH(s, &nosocks, socket_list) { + if (!check_ports(s)) + continue; + pos = xprintf("%-8s %-10s %-5s %-2s ", + "?", "?", "?", "?"); + displaysock(s, pos); + } + RB_FOREACH(s, socks_t, &socks) { + if (s->shown) + continue; + if (!check_ports(s)) + continue; + pos = xprintf("%-8s %-10s %-5s %-2s ", + "?", "?", "?", "?"); + displaysock(s, pos); } }