Google
 

Trailing-Edge - PDP-10 Archives - bb-kl11m-bm - t20src/mxnmem.b36
There are 13 other files named mxnmem.b36 in the archive. Click here to see a list.
module NMUMEM (					!Storage Management Module
		ident = 'X00.18'
		) =
begin
!	COPYRIGHT (c) DIGITAL EQUIPMENT CORPORATION 1985, 1989.
!	ALL RIGHTS RESERVED.
!
!	THIS SOFTWARE IS FURNISHED UNDER A  LICENSE AND MAY BE USED AND  COPIED
!	ONLY IN  ACCORDANCE  WITH  THE  TERMS OF  SUCH  LICENSE  AND  WITH  THE
!	INCLUSION OF THE ABOVE  COPYRIGHT NOTICE.  THIS  SOFTWARE OR ANY  OTHER
!	COPIES THEREOF MAY NOT BE PROVIDED  OR OTHERWISE MADE AVAILABLE TO  ANY
!	OTHER PERSON.  NO  TITLE TO  AND OWNERSHIP  OF THE  SOFTWARE IS  HEREBY
!	TRANSFERRED.
!
!	THE INFORMATION IN THIS  SOFTWARE IS SUBJECT  TO CHANGE WITHOUT  NOTICE
!	AND SHOULD  NOT  BE CONSTRUED  AS  A COMMITMENT  BY  DIGITAL  EQUIPMENT
!	CORPORATION.
!
!	DIGITAL ASSUMES NO  RESPONSIBILITY FOR  THE USE OR  RELIABILITY OF  ITS
!	SOFTWARE ON EQUIPMENT THAT IS NOT SUPPLIED BY DIGITAL.
!++
! Facility: LSG DECnet Network Management
!
! Abstract:
!
!	This module offers the storage management functions used for
!	dynamic memory allocation. The alogrithm employed is based upon
!	the article "Buddy Systems" by James L. Peterson and Theodore
!	A. Norman published in Communications of the ACM Volume 20,
!	Number 6 - June 1977.
!
! Environment:	TOPS10 and TOPS20 user mode, MCB RSX task mode
!
! Author: Scott G. Robinson, Creation date: 13-DEC-78
!
! Modified by:
!
!	Scott G. Robinson, 15-JUL-79 : Version X00.01
!	- Convert to XPORT interfaces and make transportable.
!	Steven M. Jenness, 21-Feb-80 : Version X00.02
!       - Change to conform to NM coding standards and needs.
!
!--
!<BLF/PAGE>
!
! Include files
!

library 'MXNLIB';			! All required definitions

%if $TOPS20
    %then
	library 'MONSYM';			! Monitor symbols

	library 'MXJLNK';			! JSYS linkage definitions
    %fi

!
! Undefine TENDEFs POINTR macro
!

%if $TOPS10 %then
undeclare %quote POINTR;
%fi

!
! Global routines
!

forward routine
    NMU$MEMORY_MANAGER;				! Define global entry points

!
! Local routines
!

forward routine
    BUDDY_ADDRESS;				! Calculate buddy address of memory block

!
! Memory block format
!
! macro:   MEMORY_BLOCK     Defines header for memory block
!

%if not $MCB
%then macro $index = $tiny_integer %;
%else macro $index = $short_integer %;
%fi

$field
    MEMORY_BLOCK_FIELDS =
	set
	QUEUE_INFO = [$sub_block (Q_HEADER_SIZE)],	! Storage list queue linkages
	INDEX = [$index],			! The SIZEINDEX for this block
	TAG = [$bit],				! Indicates ALLOCATED or AVAILABLE
	SELF = [$bit],				! Indicates LEFT or RIGHT Buddy
	PARENT = [$bit],			! Indicates LEFT or RIGHT of The Parent
	  $align (FULLWORD)
	MB_TASK = [$address],			! Address of allocating task
	MB_LIMIT = [$address],			! Address of last unit of memory block
	MB_ALLOCATION = [$short_integer],	! Number of addressable units
	  $align (FULLWORD)
	DATA = [$sub_block (0)]			! Start of useable data portion
	tes;

literal
    MB_LENGTH = $field_set_size,
    ALLOC_OVERHEAD = $field_set_units + 1;	! The length of the block header
						!  plus the terminator

macro
    MEMORY_BLOCK = BLOCK [MB_LENGTH] FIELD (MEMORY_BLOCK_FIELDS)%;

literal
    TERMINATOR = 				! Value for limit word
    %if $MCB					!  of memory block
    %then
	%O'125';				! 8 bit value for MCB
    %else
	%O'252525252525';			! 36 bit value for KL
    %fi

literal
    AVAILABLE = 0,				! Values for TAG field
    ALLOCATED = 1;

literal
    LEFT = 0,					! Values for SELF and PARENT
    RIGHT = 1;

!

literal
    SIZEINDEX = 29,				! Number of Buddy Slots
    INDEX_LIMIT = SIZEINDEX - 1;		! Number of elements to search

!
! Own storage
!

macro
    SIZE_INIT =
     0,0,4,4,4,8,12,16,24,36,52,76,112,164,240,352,
     516,756,1108,1624,2380,3488,5112,7492,10980,16092,
     23584,34564,50656 %,

    BUDDY_INDEX_INIT =
     0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,
     18,19,20,21,22,23,24,25 %;

$field
    ASL_FIELD =
	set
	ASL_QUEUE = [$sub_block (Q_HEADER_SIZE)]
	tes;

$literal
    ASL_FIELD_SIZE = $field_set_size;

own
    SIZE : vector [SIZEINDEX] INITIAL (SIZE_INIT) psect($high$),
    BUDDY_INDEX : vector [SIZEINDEX] INITIAL (BUDDY_INDEX_INIT) psect($high$),
    ASL_LST : blockvector [SIZEINDEX, ASL_FIELD_SIZE] field (ASL_FIELD);

global bind
    BLKSIZ = SIZE,
    BLKBDY = BUDDY_INDEX,
    BLKLST = ASL_LST;

!
! External references
!

external routine
    NMU$QUEUE_MANAGER;				! Queue management routines

!
! Definitions used when debugging
!

external
    %debug_data_base;

    %module_name ('NMUMEM');

!<BLF/SYNONYM %UNQUOTE =>
%global_routine ('NMU$MEMORY_RESET') : novalue =

!++
! Functional description:
!
!	This routine resets the free pool data base to empty.
!
! Formal parameters: none
!
! Routine value: none
! Side effects:
!
!	All queues on the ASL_LST are cleared.
!
!--

    begin

    local
	ASL : ref block field (ASL_FIELD);

%debug (MEMORY_CONSISTENCY,
	(TRACE_INFO ('Available storage list reset')));

    ASL = ASL_LST [0, ASL_QUEUE];

    INTERRUPT_OFF;			! Disable interrupts

    decru COUNT from SIZEINDEX to 1 do
	begin
	NMU$QUEUE_RESET (ASL [ASL_QUEUE]);
	ASL = vector [ASL [ASL_QUEUE], ASL_FIELD_SIZE];
	end;

    INTERRUPT_ON;			! Allow interrupts now

    end;				! End of NMU$MEMORY_RESET
%global_routine ('NMU$MEMORY_INITIALIZE', AMOUNT) : novalue =

!++
! Functional description
!
!	Add the specified amount of memory to the free pool
!	of the storage manager.
!
! Formal parameters
!
!	AMOUNT - the initial amount of storage to allocate
!
! Implicit inputs
!
!	SIZE - the block size array
!	ASL - the Available storage list
!
! Implicit outputs
!
!	ASL - the Available storage list
!
! Routine value: none
!
! Side effects: none
!
!--

    begin

    local
	P : ref MEMORY_BLOCK,			! Allocated block
	I;					! Size index for "P"

    %debug (MEMORY_CONSISTENCY,
            (TRACE_INFO ('Initializing %D. (%O) units in free pool', .AMOUNT, .AMOUNT)));

!
! Find size index for AMOUNT
!
    I = -1;

    incr POINTR from 1 to INDEX_LIMIT do

	if ((.AMOUNT + ALLOC_OVERHEAD) lequ .SIZE [.POINTR])
	then
	    begin
	    I = .POINTR;
	    exitloop;
	    end;

    if (.I lss 0)
    then
	begin
	TASK_ERROR ('Memory block too large to initialize');
	return ;
	end;

!
! Now allocate the block
!
    if (P = CORE_GET (.SIZE [.I])) eqla 0
    then
	begin
	TASK_ERROR ('Operating system refused memory request');
	return ;
	end;
    
    P [INDEX] = .I;
    P [TAG] = AVAILABLE;
    P [SELF] = LEFT;
    P [PARENT] = LEFT;
!  %debug (always,(
!    begin
!    P [MB_ALLOCATION] = .SIZE [.I];
!    P [MB_TASK] = 0;
!    end));

  %debug (MEMORY_CONSISTENCY,
          (TRACE_INFO_C ('Adding %D. (%O) units at %O to free pool',
                         .SIZE [.I], .SIZE [.I], .P)));

    INTERRUPT_OFF;
    NMU$QUEUE_INSERT (ASL_LST [.I, ASL_QUEUE], .P);
    INTERRUPT_ON;
    end;					! End of NMU$MEMORY_INITIALIZE
forward routine MEMORY_GET;

%global_routine ('NMU$MEMORY_GET', AMOUNT) =

begin
    local VALUE;

    INTERRUPT_OFF;
    VALUE = MEMORY_GET(.AMOUNT);
    INTERRUPT_ON;
    .VALUE
end;

%routine ('MEMORY_GET', AMOUNT) =

!++
! Functional description
!
!	Get a block of storage from dynamic memory.
!	Return its address.
!
! Formal parameters
!
!	AMOUNT - Number of words to allocate
!
! Implicit inputs
!
!	ASL - Available Storage List
!	Dynamic Memory
!
! Implicit outputs
!
!	ASL - Available Storage List
!
! Routine value
!
!	The address of the storage block or 0 if no memory available
!
! Side effects: none
!
!--

    begin

    local
	P : ref MEMORY_BLOCK,			! Allocated block
	Q : ref MEMORY_BLOCK,			! Buddy to allocated block
	I,					! Exact index for "AMOUNT"
	J;					! Index actually used from ASL

%debug (MEMORY_TRACE,
	(TRACE_INFO ('Request for %D. units', .AMOUNT)));

!
! Start off with no block allocated
!
    P = 0;
!
! Calculate index for block of size AMOUNT
!
    I = -1;

    incr POINTR from 1 to INDEX_LIMIT do

	if ((.AMOUNT + ALLOC_OVERHEAD) lequ .SIZE [.POINTR])
	then
	    begin
	    I = .POINTR;
	    exitloop;
	    end;

    if (.I lss 0)
    then
	begin
	TASK_ERROR ('Size of Memory Block Requested is too large');
	return 0
	end;

!
! Find first non-empty ASL entry, starting with
! entry pointed to by I (exact index).
!

    incr TEST_INDEX from .I to INDEX_LIMIT do

	if (P = NMU$QUEUE_REMOVE (ASL_LST [.TEST_INDEX, ASL_QUEUE])) neq 0
	then
	    begin
	    J = .TEST_INDEX;
	    exitloop;
	    end;

!
! If no memory already available .. try to initialize
! the appropriate amount from the operating system.
!

    if .P eqla 0
    then
	begin
	NMU$MEMORY_INITIALIZE (.AMOUNT);
	P = NMU$QUEUE_REMOVE (ASL_LST [.I, ASL_QUEUE]);
	J = .I;
	end;

!
! Allocate memory and (optionally) split off buddy
!

    while (.J gtr .I) do
	begin

	if (.SIZE [.BUDDY_INDEX [.J]] neq 0)
	then
	    begin
	    Q = .P + .SIZE [.BUDDY_INDEX [.J]];
	    Q [TAG] = AVAILABLE;
	    Q [PARENT] = .P [PARENT];
	    Q [SELF] = RIGHT;
	    Q [INDEX] = .J - 1;
	    P [TAG] = AVAILABLE;
	    P [PARENT] = .P [SELF];
	    P [SELF] = LEFT;
	    P [INDEX] = .BUDDY_INDEX [.J];

%debug (MEMORY_CONSISTENCY,
	(begin
	 TRACE_INFO_C (' Block at %O Index %O Self= ',.P,.P[INDEX]) ;

         if .P [SELF] eql LEFT
         then TRACE_INFO_CL ('LEFT ')
         else TRACE_INFO_CL ('RIGHT ') ;

         if .P [PARENT] eql LEFT
         then TRACE_INFO_CL ('Parent=LEFT split with')
         else TRACE_INFO_CL ('Parent=RIGHT split with') ;

	 TRACE_INFO_C (' buddy at %O Index %O Self=',.Q,.Q[INDEX]) ;

         if .Q [SELF] eql LEFT
         then TRACE_INFO_CL ('LEFT ')
         else TRACE_INFO_CL ('RIGHT ') ;

         if .Q [PARENT] eql LEFT
         then TRACE_INFO_CL ('Parent=LEFT')
         else TRACE_INFO_CL ('Parent=RIGHT') ;

         end));

	    if (.I leq .BUDDY_INDEX [.J])
	    then
		NMU$QUEUE_INSERT (ASL_LST [.Q [INDEX], ASL_QUEUE], .Q)
	    else
		begin
		NMU$QUEUE_INSERT (ASL_LST [.P [INDEX], ASL_QUEUE], .P);
		P = .Q;
		end;

	    J = .P [INDEX];
	    end
	else
	    exitloop;

	end;

    P [TAG] = ALLOCATED;
!
! Return 0 if no memory allocated.
! Return address of zeroed data portion of allocated
!  block if allocation was successful.
!
    %debug (MEMORY_TRACE,
	    (if (.P eqla 0)
	     then TRACE_INFO_C ('Allocation failure')
	     else TRACE_INFO_C ('Allocated %D. units at %O',
                              .SIZE [.P[INDEX]], P [DATA])));

    (if (.P eqla 0) then
	begin
	    TASK_ERROR ('Memory request failed');
	    0
	end
	 else
	begin
	local
	    A : ref block,
	    CNT;

	CNT = .AMOUNT;
	P [MB_TASK] = CURRENT_TASK;
	P [MB_ALLOCATION] = .CNT;
	P [MB_LIMIT] = P [DATA] + .CNT;		! Address of terminator
	P = P [DATA];
	A = .P;

	do (A [0, 0, %bpunit, 0] = 0; A = .A + 1) while (CNT = .CNT - 1) neq 0;

	A [0, 0, %bpunit, 0] = TERMINATOR;	! Mark end of block
	.P
	end
    )
    end;					!End of NMU$MEMORY_GET
forward routine MEMORY_RELEASE : novalue;

%global_routine ('NMU$MEMORY_RELEASE', P, AMOUNT) : novalue =

begin
    INTERRUPT_OFF;
    MEMORY_RELEASE (.P, .AMOUNT);
    INTERRUPT_ON
end;

%routine ('MEMORY_RELEASE', P, AMOUNT) : novalue =

!++
! Functional description
!
!	Returns a block of memory to the ASL.
!
! Formal parameters
!
!	P - address of memory block to return
!	AMOUNT - Size of memory block
!
! Implicit inputs
!
!	ASL - the Available Storage List
!
! Implicit outputs
!
!	ASL - the Available Storage List
!
! Routine value: none
! Side effects:	none
!
!--

    begin

    map
	P : ref MEMORY_BLOCK;

    local
	Q : ref MEMORY_BLOCK,
	R,
	T : ref MEMORY_BLOCK;

    %debug (MEMORY_TRACE,
 	    (TRACE_INFO ('Releasing %D. units at %O',
                         .AMOUNT,.P)));

!
! Remove Allocation Overhead amount to obtain real MEMORY_BLOCK address
!
    T = .P - (ALLOC_OVERHEAD - 1);

!
! Check to make sure block is actually allocated and not corrupted.
!

    if (.T [TAG] neq ALLOCATED) or
       (.T [MB_ALLOCATION] nequ .AMOUNT) or
       (.T [MB_LIMIT] neqa (T [DATA] + .T [MB_ALLOCATION])) or
       (.(.T [MB_LIMIT])<0,%bpunit,0> neq TERMINATOR)
    then
	begin
	%if not $MCB
	%then
	TRACE_INFO ('Error detected while releasing %D. units of memory',
			.AMOUNT);
	TRACE_INFO_C ('Block begins at %O; header starts at %O',
			T [DATA],
			.T);
	TRACE_INFO_C ('Header shows %D. units',
			.T [MB_ALLOCATION]);
	TRACE_INFO_C ('Allocation flag is %O (1=allocated, 0=available)',
			.T [TAG]);
	TRACE_INFO_C ('Header shows units were allocated by task at %O',
			.T [MB_TASK]);
	TRACE_INFO_C ('Header shows limit word:  %O / %O',
			.T [MB_LIMIT],
			..T [MB_LIMIT]);
	TRACE_INFO_C ('Limit word should contain:  %O',
			TERMINATOR);
	%fi
	TASK_ERROR ('Memory database inconsistency');
	return ;
	end;

!
! Tag this block as available now.
!

    T [TAG] = AVAILABLE;

!
! Try to find Buddy and form with it
!
    Q = BUDDY_ADDRESS (.T);

    while (.Q neqa 0) do
	begin


%debug (MEMORY_CONSISTENCY,
	(begin

	 TRACE_INFO_C (' Block at %O Index %O Self= ',.T,.T [INDEX]) ;

         if .T [SELF] eql LEFT
         then TRACE_INFO_CL ('LEFT ')
         else TRACE_INFO_CL ('RIGHT ') ;

         if .T [PARENT] eql LEFT
         then TRACE_INFO_CL ('Parent=LEFT merged with')
         else TRACE_INFO_CL ('Parent=RIGHT merged with') ;

         TRACE_INFO_C (' buddy at %O Index %O Self=',.Q,.Q[INDEX]) ;

         if .Q [SELF] eql LEFT
         then TRACE_INFO_CL ('LEFT ')
         else TRACE_INFO_CL ('RIGHT ') ;

         if .Q [PARENT] eql LEFT
         then TRACE_INFO_CL ('Parent=LEFT')
         else TRACE_INFO_CL ('Parent=RIGHT');

         end));
	if not NMU$QUEUE_EXTRACT (ASL_LST [.Q [INDEX], ASL_QUEUE], .Q)
	then
	    begin
	    TASK_ERROR ('Available storage list corrupted');
	    return ;
	    end;

	if (.T gtra .Q)
	then
	    begin
	    R = .T;
	    T = .Q;
	    Q = .R
	    end;

	T [TAG] = AVAILABLE;
	T [SELF] = .T [PARENT];
	T [PARENT] = .Q [PARENT];
	T [INDEX] = 1 + .Q [INDEX];
	Q = BUDDY_ADDRESS (.T);
	end;

    NMU$QUEUE_INSERT (ASL_LST [.T [INDEX], ASL_QUEUE], .T);

    end;					! End of NMU$MEMORY_RELEASE
%routine ('BUDDY_ADDRESS', P) =

!++
! Functional description
!
!	Calculate and return address of buddy of Memory block at address P.
!
! Formal parameters
!
!	P - Address of a memory block
!
! Implicit inputs
!
!	SIZE - size of various memory blocks
!	Dynamic Memory
!
! Implicit outputs: none
!
! Routine value:
!
!	The address of the buddy to P or 0 if none
!
! Side effects: none
!
!--

    begin

    map
	P : ref MEMORY_BLOCK;			! Designated block

    local
	Q : ref MEMORY_BLOCK,			! Buddy block
	J;					! Size index for buddy

!
! Process according to whether block is a LEFT
! or RIGHT buddy.
!

    if (.P [SELF] eql LEFT)
    then
	begin
	Q = .P + .SIZE [.P [INDEX]];

	if ((.Q geqa .MEMSIZE) or (.Q [SELF] eql LEFT)) then return 0;

	end
    else
	begin
	J = .BUDDY_INDEX [.P [INDEX] + 1];
	Q = .P - .SIZE [.J];

	if (.Q [INDEX] neq .J) then return 0;

	end;

    if (.Q [TAG] eql ALLOCATED) then return 0;

    .Q
    end;					! End of BUDDY_ADDRESS
end						! End of module MEMORY

eludom
! Local Modes:
! Mode:Fundamental
! Comment Start:! 
! Comment Column:40
! Comment Rounding:+1
! Auto Save Mode:2
! End: