From: Maxime Devos <maximedevos@telenet.be>
To: Maxim Cournoyer <maxim.cournoyer@gmail.com>,
Danny Milosavljevic <dannym@scratchpost.org>
Cc: 44944@debbugs.gnu.org
Subject: bug#44944: Unable to log into X session via gdm
Date: Sun, 25 Sep 2022 13:47:15 +0200 [thread overview]
Message-ID: <d6954217-2778-f161-87e0-882356ea4ebd@telenet.be> (raw)
In-Reply-To: <8735crdu0p.fsf@gmail.com>
[-- Attachment #1.1.1: Type: text/plain, Size: 2097 bytes --]
On 16-09-2022 21:00, Maxim Cournoyer wrote:
> That'd be cool, but how would you implement such a hash, that returns
> something fixed between 0 and 1024? That doesn't sound feasible,
> although I'm no hash function expert.
Remember that any function from X to a finite set Y is a hash function
-- this included very simple ones like e.g. X={1,...,N}, Y={1,...,N},
map every number \(k\) to \(k\).
You can't implement such a hash without hash collisions, due to the
pigeonhole principle, as there are more inputs (user names) that outputs
(numbers between 0 and 1024).
Users can't share uids, so hash collisions are unacceptable.
As collisions are unacceptable (and not just tolerable but disliked),
the 'uniformity' property of some hash functions is unneeded.
If we limit ourselves to only having 1025 users in total, then with some
care there aren't any hash collisions (see proposal by bokr) (*), but
that would place a limit on how many services can be written for Guix.
Of course, an individual system might only have < 1025 users as not all
services are enabled, but then the hash function would depend on the
system in question. However, Guix cannot tell in advance what usernames
will be used in the future, so it would need to gradually build up its
hash function (state!) and remember old 'deleted' users (state!).
But if you have to remember the old users anyway and gradually build up
a hash function, then you might as well simplify things by not going for
a classically "good" hash function but rather a simple table that is
gradually build up (technically a hash function), as I've tried out in
<https://issues.guix.gnu.org/36508#21> (currently limited to uids, gid
not yet supported, also largely untested).
(*) Implementation:
(define (hash username)
(define %table
`(("root" . 0)
("foo" . 1)
("bar" . 2)
; <insert entries for all other (system) usernames in Guix here>
[...]))
(or (assoc-ref %table username)
(error "doesn't exist")))
Greetings,
Maxime.
[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 929 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]
next prev parent reply other threads:[~2022-09-25 12:22 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-11-29 13:02 bug#44944: Unable to log into X session via gdm Danny Milosavljevic
2020-11-29 17:00 ` Marius Bakke
2020-11-29 21:20 ` Danny Milosavljevic
2022-09-16 19:00 ` Maxim Cournoyer
2022-09-16 21:03 ` Maxim Cournoyer
2022-09-20 14:49 ` bokr
2022-09-22 4:11 ` Maxim Cournoyer
2022-09-25 11:47 ` Maxime Devos [this message]
2022-09-27 0:12 ` Maxim Cournoyer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://guix.gnu.org/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d6954217-2778-f161-87e0-882356ea4ebd@telenet.be \
--to=maximedevos@telenet.be \
--cc=44944@debbugs.gnu.org \
--cc=dannym@scratchpost.org \
--cc=maxim.cournoyer@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/guix.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).