From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 8476 invoked from network); 23 Jul 2021 23:04:38 -0000 Received: from minnie.tuhs.org (45.79.103.53) by inbox.vuxu.org with ESMTPUTF8; 23 Jul 2021 23:04:38 -0000 Received: by minnie.tuhs.org (Postfix, from userid 112) id A73239CAAB; Sat, 24 Jul 2021 09:04:34 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id D15899CAA5; Sat, 24 Jul 2021 09:03:51 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=planet.nl header.i=@planet.nl header.b="oEeNxWQA"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 6C4E19CAA5; Sat, 24 Jul 2021 09:03:45 +1000 (AEST) Received: from cpsmtpb-ews06.kpnxchange.com (cpsmtpb-ews06.kpnxchange.com [213.75.39.9]) by minnie.tuhs.org (Postfix) with ESMTP id B0B089CAA4 for ; Sat, 24 Jul 2021 09:03:39 +1000 (AEST) Received: from cpsps-ews30.kpnxchange.com ([10.94.84.196]) by cpsmtpb-ews06.kpnxchange.com with Microsoft SMTPSVC(8.5.9600.16384); Sat, 24 Jul 2021 01:03:35 +0200 X-Brand: 7abm2Q== X-KPN-SpamVerdict: e1=0;e2=0;e3=0;e4=;e6=(e1=10;e3=10;e2=11;e4=10;e6=1 0);EVW:White;BM:NotScanned;FinalVerdict:Clean X-CMAE-Analysis: v=2.4 cv=EdSr/NqC c=1 sm=1 tr=0 ts=60fb4ac7 cx=a_idp_e a=aIJzBKXFL4aO3PtWP49Erg==:117 a=soxbC+bCkqwFbqeW/W/r+Q==:17 a=x1i13A_MHe4A:10 a=IkcTkHD0fZMA:10 a=e_q4qTt1xDgA:10 a=YQ40WqKhAAAA:20 a=u72O05gKAAAA:8 a=r99ltje59Bn8x4vE60EA:9 a=QEXdDO2ut3YA:10 a=N9M9Gv0imjkMJp2kB0A3:22 X-CM-AcctID: kpn@feedback.cloudmark.com Received: from smtp.kpnmail.nl ([195.121.84.43]) by cpsps-ews30.kpnxchange.com over TLS secured channel with Microsoft SMTPSVC(8.5.9600.16384); Sat, 24 Jul 2021 01:03:35 +0200 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=planet.nl; s=planet01; h=to:date:message-id:subject:mime-version:content-type:from; bh=eRhDvgaUeR08Q14hDuuIwvs6fT9gt07brS4qiZxjxqw=; b=oEeNxWQA/Gp8jyVXjcfh33HC6cuR2nv+xGZDhzKneDVCd8jX77Z9IXxgglzeOv6cv1n19UnaHykzr nWpE7ntd14TZkgqxkUSUyfFEJpJcux64e5P70VRawHMHLuU0mSKRzG3AEWRwuguRpjuYYXsFrTrgv8 QiBt0j9dkmr27iKU= X-KPN-MID: 33|OJf7xY/3wCPAA/3i0R2nOPP/+ow430ovbLaDT6oIJvlAJbtZpNR/aPgZkflpRcG ViqUCxHv8Fq8LPuNlRyPdpazTf+BgKlrdXvjmXvLuy/0= X-KPN-VerifiedSender: Yes X-CMASSUN: 33|gkXG0x0vbmzVm2xzyjmzz85bWYmaP9Rl/btRGQSnlZu1o9QMQkFbfc8cyC7riLI 2Z4wBpEpENf8Bzq+Ev2Q3cA== X-Originating-IP: 80.101.112.122 Received: from mba1.fritz.box (sqlite.xs4all.nl [80.101.112.122]) by smtp.kpnmail.nl (Halon) with ESMTPSA id 34ea5f3a-ec0a-11eb-b98e-005056ab1411; Sat, 24 Jul 2021 01:03:35 +0200 (CEST) From: Paul Ruizendaal Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.7\)) Message-Id: Date: Sat, 24 Jul 2021 01:03:34 +0200 To: norman@oclsc.org X-Mailer: Apple Mail (2.3445.9.7) X-OriginalArrivalTime: 23 Jul 2021 23:03:35.0211 (UTC) FILETIME=[F6FCAFB0:01D78016] X-RcptDomain: minnie.tuhs.org Subject: [TUHS] Triangulating 32V with paging X-BeenThere: tuhs@minnie.tuhs.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: The Unix Heritage Society mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: TUHS main list Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" > Sat Aug 31 06:21:47 AEST 2019 > John Reiser did do his own paging system for UNIX 32/V. > I heard about it from friends at Bell Labs ca. 1982-83, > when I was still running systems for physicists at Caltech. > It sounded very interesting, and I would love to have had > my hands on it--page cache unified with buffer cache, > copy-on-write from the start. >=20 > [...] >=20 > It is in any case a shame that jfr's code never saw the light > of day. I really hope someone can find it on an old tape > somewhere and we can get it into the archive, if only because > I'd love to look at it. >=20 > Norman Wilson > Toronto ON Norman, I am getting more optimistic that much of this version of 32V can be = =E2=80=98triangulated=E2=80=99 from the surviving sources. For = convenience I call this version =E2=80=9C32V r3=E2=80=9D (with the first = swapping version being "32V r1" and the scatter loading version being = "32V r2"). I=E2=80=99ve been reading my way through the surviving 32/V r2, = SysIII-Vax, SVr1-Vax and SVr2-Vax sources. There seems to be a lot of = continuous progression in these versions. =46rom a communication with = Keith Kelleman I thought that VM in SVr2 was unrelated, but that appears = to have been a misunderstanding. In short, it seems that the basic = paging algorithms and data structures in SVr2 (other than the region = abstraction) come from 32V r3. The strongest clue for the source link is in the SVr2 =E2=80=9Cpage.h=E2=80= =9D file. In it, the union describing a page table entry matches with = JFR=E2=80=99s description and is otherwise (partially) unused in SVr2. = There are other, similar clues in the other source trees. To explain more clearly, have a look at this code section: = https://github.com/ryanwoodsmall/oldsysv/blob/master/sysvr2-vax/src/uts/va= x/sys/page.h#L61-L106 In this union, the 2nd struct =E2=80=9Cpgd=E2=80=9D is never used, nor = is the bit pg_disk in the =E2=80=9Cpgm=E2=80=9D struct ever used. It = matches with JFR=E2=80=99s recollection: My internal design strategy was to use the hardware page table entry (4 bytes per page, with "page not present" being one bit which freed the other 31 bits for use by software) as the anchor to track everything about a page. This resulted in a complicated union of bitfield structs, which became a headache. When other departments took over the work, the first thing they did was use 8 bytes per page, which meant shuffling between the software and the hardware descriptors: its own mess. In the pte as given, a pte can be in two states: (i) the pg_disk bit is = reset in which case it is in =E2=80=9Cpgm=E2=80=9D format - this format = is recognized by the mmu hardware; (ii) the pg_disk bit is set in which = case it is in =E2=80=9Cpgd=E2=80=9D format. When a page is paged in, the = disk form of the pte was I think saved in the page frame descriptor (the = =E2=80=9Cpfdat" table) and the pte converted to the memory form. Upon = page-out the reverse happened. In the SVr2 version of this code the = =E2=80=9Cpgd=E2=80=9D form is abandoned and replaced by the separate = disk descriptors (see = https://github.com/ryanwoodsmall/oldsysv/blob/master/sysvr2-vax/src/uts/va= x/sys/region.h#L104-L114) The =E2=80=9Cpgd=E2=80=9D structure is a bit puzzling. There is a 19 bit = device block number, which is less than the 24 bits allowed by the = filesystem code and also less than the 20 bits that would fit in the = pte. Maybe this is because the RP04/RP05 disks of the early 80=E2=80=99s = worked with 19 bits. I am not sure what the =E2=80=9Cpg_iord=E2=80=9D = field is about. The comment =E2=80=9Cinode index=E2=80=9D may be = misleading. My hypothesis that it is a short form of the device code, = for instance an index into the mount table; magic values could have been = used to identify the swap device, =E2=80=9Cdemand zero=E2=80=9D, etc. It seems probable to me that the paging algorithm in SVr2 was derived = from the 32/V r3 algorithm. John's recollection: Our machine started with 512KB of RAM, but within a few months was = upgraded to 4 MB with boards that used a new generation of RAM chips. The hardware page size was 512 bytes, which is quite small. Strict LRU on 8,192 pages, plus Copy-On-Write, made the second reference to a page "blindingly fast". In a follow up mail conversation with JFR we (I?) arrived at the = conclusion that literal =E2=80=9Cstrict LRU=E2=80=9D is not likely on = VAX hardware, but that an algorithm that maintains a small working set = combined with a large second chance list amounts to about the same. It = seems to me that this description also applies to the surviving SVr2 = implementation: every 4 seconds sweep through the page tables of all = processes and pages that were not referenced are moved to the free/2nd = chance list. To implement this it seems likely to me that 32V r3 used a structure = similar to this: = https://github.com/ryanwoodsmall/oldsysv/blob/master/sysvr2-vax/src/uts/va= x/sys/pfdat.h#L4-L13 Such a structure is also in line with viewing core = as a cache for disk, similar to TENEX that JFR had in mind. The big change from SysIII to SVr1 in kernel page table management is = the introduction of the =E2=80=9Csptmap=E2=80=9D = (https://chiselapp.com/user/pnr/repository/paging/file?name=3Dos/machdep.c= &ci=3Dfba821c0b38e2e350da927347eba25d5fe53852c&ln=3D346,378). In 32V r2 = and SysIII the user page tables are swapped in and out of kernel space = along with the _u area. This makes it impractical to do the working set = sweep every few seconds. The =E2=80=9Csptmap=E2=80=9D innovation = effectively creates a global page table space that fits with the needs = of the working set sweep. In SVr1 it seems to have no real benefit, and = it seems likely to me that it came from 32V r3. In general it seems plausible to me that SVr1 derives from 32V r3, but = was regressed to SysIII code where necessary to keep the code PDP-11 = compatible. Another clue for this is in the buffer code of SVr1: = https://chiselapp.com/user/pnr/repository/paging/file?name=3Dos/main.c&ci=3D= fba821c0b38e2e350da927347eba25d5fe53852c&ln=3D205,218 Here, the disk buffers are allocated as virtual memory pages, not as an = array. This too is otherwise unused in SVr1, but makes perfect sense in = the context of 32V r3. So, in summary, it would seem to me that the 32V r3 virtual memory = system: - used sptmap code similar to SVr1/r2 to manage page tables in the = kernel - used the pte structure from SVr2 and a pfdat table similar to SVr2 to = manage mappings - used page stealer and fault code similar to SVr2 Phrased the other way around: SVr2-vax seems to use the 32V r3 virtual = memory code with the region abstraction added on top, and the unified = buffer removed. At the moment I have not found clear clues for the unified buffer = algorithms or mmap implementation. Perhaps careful reading of the IPC = shared memory code in SVr1 will yield some. To be continued =E2=80=A6=20