How does memory management work in the Sega Megadrive?

Discussion in 'Discussion & Q&A' started by ErotemeObelus, May 23, 2019.

  1. ErotemeObelus

    ErotemeObelus Newcomer Trialist

    Joined:
    May 18, 2019
    Messages:
    2
    Almost all modern processors are recreations of the PDP-11 microprocessor, because that was the processor for which the semantics of the C programming language were based on. One of the distinctions the PDP-11 made was between the stack (memory area designated for variables and arrays whose structure was known before runtime) and the heap (memory area designated for arrays whose size can only be known during runtime; dynamic memory). The assembly of the PDP-11 treats stack memory and heap memory differently.

    In the 68k for the Sega Genesis, how is the distinction between the stack and the heap drawn? How is dynamic memory that can only be known at runtime managed?
     
  2. MainMemory

    MainMemory Well-Known Member Member

    Joined:
    Mar 29, 2011
    Messages:
    848
    The 68000 on the MD has a flat 64KB of RAM, the usage of which is managed manually by the code in the cartridge ROM. There is a dedicated stack, but it can be placed at any location in RAM and moved anywhere at any time, and it is up to the programmer to know how large the stack is and prevent overflows. Because there is no OS to provide memory management functions, games tend to divide the RAM into various fixed areas, for example Sonic 2/3K reserve the first 32KB for the current level's chunk data (S1 reserves more). The only thing you could call dynamic allocation in Sonic games is the object system, which still uses a fixed area of RAM divided into slots, and "allocating" an object is simply a matter of finding a slot within the buffer that has no object loaded to it.
     
  3. FireRat

    FireRat "The grand imitator..." Member

    Joined:
    Oct 31, 2009
    Messages:
    535
    As MainMemory said, on MD you have all 64kb free for programmer's manual use, and there's the dedicated stack pointer register, which you can set to any RAM address through the first longword from 68k header or by setting the address manually in Assembly. In original games, buffers (like the one for objects or tileset data) and variables are allocated statically through the assembler; you can see a similar example in the current Sonic 2 disassembly, or you can just refer to the hex addresses directly. If you're running out of RAM though, you can recycle addresses that are not used at the moment, for example, the Special Stage from Sonic 1 can take a part from the level tileset buffer, because none is shown at that moment. It's just the best way to take a good approach from the hardware, RAM access isn't that fast, and that's a major hurdle for C (for which M68k has not been designed for, AFAIK), that rely on stack for holding variables and parsing them across functions (if you care about speed, you'd not like to rely on recursion)

    That said, this could just be another coding style; if you're looking for a traditional workflow that does memory management, there's SGDK, where you can code in C, includes a malloc() function, and so on.
     
  4. Clownacy

    Clownacy Grumpy Staff

    Joined:
    Aug 15, 2014
    Messages:
    869
    ...I've never heard of heap memory management being a hardware feature before. I thought that was just a C standard library thing.
     
  5. LazloPsylus

    LazloPsylus A Certain Scientific Railgun The Railgun

    Joined:
    Nov 25, 2009
    Messages:
    Location:
    Academy City
    "Stack" and "Heap" are software-defined constructs. No memory management is available unless the language used implements it, or a memory manager is coded. As there's no variable amounts of RAM available, memory management is generally not needed, either. As assembly is generally used directly for the console, memory management is handled entirely by hand.
     
    FireRat likes this.
  6. ErotemeObelus

    ErotemeObelus Newcomer Trialist

    Joined:
    May 18, 2019
    Messages:
    2
    EDIT: I was wrong. See LazloPsylus's post.

    They're not software-defined constructs. There's a common oversimplification of computing systems. Most people and popular culture teaches that computing occurs at two levels:
    1. Hardware
    2. Software
    In reality, there are actually three levels of computing systems.
    1. Hardware
    2. Computer microarchitecture
    3. Software
    Computer microarchitecture is neither hardware nor software. It is its own unique level. The division between stack and heap came from the computer microarchitecture of the PDP-11, which is what stdlib.h was designed around. As a result of the celebrity of both UNIX, C, & the PDP-11, virtually every modern computing system uses the computer microarchitecture of the PDP-11 and consequentially has a partition between the stack and the heap. Better-designed computer microarchitectures do not need to make a distinction between the stack and the heap.
     
    Last edited: Jun 10, 2019
  7. LazloPsylus

    LazloPsylus A Certain Scientific Railgun The Railgun

    Joined:
    Nov 25, 2009
    Messages:
    Location:
    Academy City
    EDIT #2: After some cajoling, I've brought it back, as people want to learn more. So here's a more thorough version of the original post:

    Alright, let's break down this chaotic mass of complexity, because... yeah, no, that's not how it works. At all.

    Within the context of a computing architecture, there are two major groupings for which all layers fall into:

    - Hardware
    - Software

    There is some argument about where programmable logic falls (some consider it hardware, others consider it software, still others consider it both), but for the sake of simplicity, we're ignoring that, as it's also not terribly relevant to the subject at hand. Within hardware, there's three primary layers common across computing architectures:

    - Instruction Set Architecture (ISA)
    - Microarchitecture
    - System Design

    There are additional layers that can go into hardware, but those are far less standard and really tie into more unique characteristics behind certain architectures (hello, x86 and your sub-architectures...), and dig too deep into the underyling subjects to be adequately explainable or beneficial to this thread. Notice where your "computer microarchitecture" lands. Well within hardware. Additionally, microarchitecture is how an ISA is implemented, which introduces per-model and per-revision differences between chips within the same family using the same code.

    As to how this all ties into the issue at hand, we're getting to that. Within the hardware layer, there is such a thing as a "stack". However, it's functionality is quite basic, and generally not isolated from the rest of accessible address space. Put simply, stacks are simple LIFO (Last In, First Out) queues, and a processor generally only looks at it in terms of a stack pointer, which is a dedicated register. For the Motorola 68000 family, that dedicated register is A7. For the PDP-11 (your reference point of preference), that would be register R6 for its primary processor, the KA11. Again, none of the stack at the processor level has any isolation or really any differentiation from the rest of address space, but is just a location pointed to for the processor to store data in a LIFO queue.

    If you're looking for isolation of address space, then there's several items to look into. There's the concepts of memory segmentation and memory paging, which are different methods of isolating and dedicating memory space (segmentation by assigning regions of memory "segment IDs" and referencing memory based on offsets of that segment ID, paging by constructing contiguous segments of memory virtually with chunks [pages] that may or not be contiguous in the actual physical memory space), and both of these can be handled at a software level through standard libraries relied on for runtime (see: C standard library) as well as through hardware (Memory Management Units). Memory virtualization is what creates the memory isolation you're referring to, and creates the discrete "stack" and "heap" memory spaces.

    To make this clear, this means that the processor, itself, is not responsible for any such firm assignments. Instead, that is the job of an integrated MMU and/or a language's runtime environment, which involves foundational implementations for a language that abstract such operations into a form of standardization. Processors such as the KA11 (which is the central processor of the PDP-11 you continue to refer back to) do not handle any memory abstraction or isolation.

    Finally, to shoot down the complete misrepresentation of the PDP-11 itself. As I've pointed out, the PDP-11 is not a microprocessor. Instead, if you've actually read the manual, the PDP-11 is in reference to an entire system. The microprocessor of the PDP-11, as mentioned, is the KA11. Your mis-representation of the PDP-11 as a processor when it instead refers to an entire system undermines the stability of your argument, as it demonstrates a lack of understanding of the subject matter and/or a disingenuous argument.

    Here's some sources of information to back up my explanation:
    http://gordonbell.azurewebsites.net/digital/pdp 11 handbook 1969.pdf
    http://pages.cs.wisc.edu/~remzi/OSTEP/
    Structured Computer Organization, Andrew S. Tanenbaum, ISBN 0-13-148521-0
    Operating Systems: Internals and Design Principles, William Stallings, ISBN 0-13-147954-7

    These are just a few items one can dig into to cover the subject at a depth much further than I have the patience or effort to, as well as a scan of the PDP-11 handbook, which explains specifically what comprises the PDP-11 system.
     
    Last edited: Jun 9, 2019
  8. MarkeyJester

    MarkeyJester ! % # @ Member

    Joined:
    Jun 27, 2009
    Messages:
    2,711
    Honestly, you should've kept it in (or at least spoiler tag it), I thought it was an interesting read irrelevant of whether or not it served its purpose of getting the point across to the appropriate party.
     
    Natsumi likes this.
  9. LazloPsylus

    LazloPsylus A Certain Scientific Railgun The Railgun

    Joined:
    Nov 25, 2009
    Messages:
    Location:
    Academy City
    Meh, decided not to restore the old one, but provided a much better version with sources. A few people talked me into it. Please learn something from it.
     
    Natsumi likes this.