| 1 | #!/usr/bin/perl | ||||||||||||||||||||||||||||
| 2 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||
| 3 | # Buddy system memory allocation in 100% Pure Perl | ||||||||||||||||||||||||||||
| 4 | # Philip R Brenan at gmail dot com, Appa Apps Ltd, 2016 | ||||||||||||||||||||||||||||
| 5 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||||||
| 7 | package Data::Layout::BuddySystem; | ||||||||||||||||||||||||||||
| 8 | 1 | require v5.16.0; | |||||||||||||||||||||||||||
| 9 | 1 | ▶ | use warnings FATAL => qw(all); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 10 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 11 | 1 | ▶ | use Data::Table::Text qw(:all); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 12 | 1 | ▶ | use Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 13 | 1 | our $VERSION = 20170808; | |||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||
| 15 | 1 | if (0) # Save to S3:- this will not work, unless you're me, or you happen, to know the key | |||||||||||||||||||||||||||
| 16 | {my $z = 'DataLayoutBuddySystem.zip'; | ||||||||||||||||||||||||||||
| 17 | print for qx(zip $z $0 && aws s3 cp $z s3://AppaAppsSourceVersions/$z && rm $z); | ||||||||||||||||||||||||||||
| 18 | } | ||||||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||||||
| 20 | #1 Methods | ||||||||||||||||||||||||||||
| 21 | sub new # Create a new Buddy system | ||||||||||||||||||||||||||||
| 22 | 76 | ▶ | {return bless {}; | ||||||||||||||||||||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 23 | } | ||||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||
| 25 | 52380 | ▶ | sub freeChains{$_[0]{freeChains} //= []} ## Addresses of free blocks organised by power of two size | ||||||||||||||||||||||||||
|
Subroutine
freeChains: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"freeChains"} //= []
MC/DC100%1/1
$_[0]{"freeChains"} //= []
$_[0]{"freeChains"}
Truth table100%2/2
A
A= $_[0]{"freeChains"}
| |||||||||||||||||||||||||||||
| 26 | 4427 | ▶ | sub usedSize {$_[0]{usedSize} //= {}} ## {address} = size of allocation at that address | ||||||||||||||||||||||||||
|
Subroutine
usedSize: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"usedSize"} //= {}
MC/DC100%1/1
$_[0]{"usedSize"} //= {}
$_[0]{"usedSize"}
Truth table100%2/2
A
A= $_[0]{"usedSize"}
| |||||||||||||||||||||||||||||
| 27 | 974 | ▶ | sub wentTo {$_[0]{wentTo} //= {}} ## {address1} = address2 - where address 1 was relocated to by copy | ||||||||||||||||||||||||||
|
Subroutine
wentTo: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"wentTo"} //= {}
MC/DC100%1/1
$_[0]{"wentTo"} //= {}
$_[0]{"wentTo"}
Truth table100%2/2
A
A= $_[0]{"wentTo"}
| |||||||||||||||||||||||||||||
| 28 | 991 | ▶ | sub cameFrom {$_[0]{cameFrom} //= {}} ## {address1} = address2 - where address 1 came from before being copied | ||||||||||||||||||||||||||
|
Subroutine
cameFrom: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"cameFrom"} //= {}
MC/DC100%1/1
$_[0]{"cameFrom"} //= {}
$_[0]{"cameFrom"}
Truth table100%2/2
A
A= $_[0]{"cameFrom"}
| |||||||||||||||||||||||||||||
| 29 | 18415 | ▶ | sub allFrees {$_[0]{allFrees} //= []} ## [chain] = count of allocations minus frees on this chain | ||||||||||||||||||||||||||
|
Subroutine
allFrees: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"allFrees"} //= []
MC/DC100%1/1
$_[0]{"allFrees"} //= []
$_[0]{"allFrees"}
Truth table100%2/2
A
A= $_[0]{"allFrees"}
| |||||||||||||||||||||||||||||
| 30 | 45 | ▶ | sub nameAlloc {$_[0]{nameAlloc} //= {}} ## {name} = name of allocation if a name has been supplied | ||||||||||||||||||||||||||
|
Subroutine
nameAlloc: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"nameAlloc"} //= {}
MC/DC100%1/1
$_[0]{"nameAlloc"} //= {}
$_[0]{"nameAlloc"}
Truth table100%2/2
A
A= $_[0]{"nameAlloc"}
| |||||||||||||||||||||||||||||
| 31 | 45 | ▶ | sub allocName {$_[0]{allocName} //= {}} ## {address} = name of allocation at this address if a name has been supplied | ||||||||||||||||||||||||||
|
Subroutine
allocName: called CC=2 SCAR=6.9
Pod
undocumented
Condition100%2/2
$_[0]{"allocName"} //= {}
MC/DC100%1/1
$_[0]{"allocName"} //= {}
$_[0]{"allocName"}
Truth table100%2/2
A
A= $_[0]{"allocName"}
| |||||||||||||||||||||||||||||
| 32 | 11160 | ▶ | sub size {scalar @{$_[0]->freeChains}} ## Number of free chains in use | ||||||||||||||||||||||||||
|
Subroutine
size: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||
| 34 | sub allocField($$$) # Allocate a block in the buddy system, give it a name that is invariant even after this buddy system has been copied to a new buddy system to compact its storage, and return the address of its location in the buddy system | ||||||||||||||||||||||||||||
| 35 | 18 | ▶ | {my ($buddySystem, $name, $size) = @_; # Buddy system, name of block, integer log2(size of allocation) | ||||||||||||||||||||||||||
|
Subroutine
allocField: called CC=4 SCAR=14.2
Pod
documented
| |||||||||||||||||||||||||||||
| 36 | 18 | ▶ | $name or # Check name has been supplied | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 37 | confess "Name required"; | ||||||||||||||||||||||||||||
| 38 | 18 | ▶ | $name =~ /\A\w+\Z/ or # Check that only word characters are being used to construct the field name | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 39 | confess "Name must consist of word characters, not: $name"; | ||||||||||||||||||||||||||||
| 40 | 18 | ▶ | defined($buddySystem->nameAlloc->{$name}) and # Check proposed name of allocation is not already in use | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 41 | confess "Name already defined: $name"; | ||||||||||||||||||||||||||||
| 42 | 18 | my $alloc = $buddySystem->alloc($size); # Perform allocation | |||||||||||||||||||||||||||
| 43 | 18 | $buddySystem->nameAlloc->{$name} = $alloc; # Name to address of allocation | |||||||||||||||||||||||||||
| 44 | 18 | $buddySystem->allocName->{$alloc} = $name; # Address to name of allocation | |||||||||||||||||||||||||||
| 45 | 18 | $alloc # Return address of allocation | |||||||||||||||||||||||||||
| 46 | } # allocField | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | sub alloc($$) # Allocate a block and return its bit address | ||||||||||||||||||||||||||||
| 49 | 1117 | ▶ | {my ($buddySystem, $size) = @_; # Buddy system, integer log2(size of allocation) | ||||||||||||||||||||||||||
|
Subroutine
alloc: called CC=12 SCAR=24.9
Pod
documented
| |||||||||||||||||||||||||||||
| 50 | 1117 | ▶ | $size >= 0 or confess "Size must be positive, not $size"; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 51 | 1117 | ▶ | $size == int($size) or confess "Size must be integral, not $size"; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 52 | 1117 | $buddySystem->allFrees->[$size]++; # Count allocations and frees on this chain - alloc always works | |||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||
| 54 | 1117 | ▶ | if ($buddySystem->size == 0) # Initial allocation | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 55 | 76 | {my $alloc = 0; # Allocation address | |||||||||||||||||||||||||||
| 56 | 76 | $buddySystem->freeChains->[$size] = {}; # Create chain for initial allocation | |||||||||||||||||||||||||||
| 57 | 76 | $buddySystem->usedSize->{$alloc} = $size; # Save size of allocation at offset | |||||||||||||||||||||||||||
| 58 | 76 | return $alloc; # Return allocation | |||||||||||||||||||||||||||
| 59 | } | ||||||||||||||||||||||||||||
| 60 | |||||||||||||||||||||||||||||
| 61 | 1041 | for my $F($size..$buddySystem->size-1) # Look for space on the free chains | |||||||||||||||||||||||||||
| 62 | 1932 | ▶ | {if (my $f = $buddySystem->freeChains->[$F]) # Each chain | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 63 | 1885 | ▶ | {if (keys %$f) # Free chain with space | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 64 | 949 | {for my $alloc(sort {$a <=> $b} keys %$f) # Allocation address | |||||||||||||||||||||||||||
| 65 | 949 | {delete $f->{$alloc}; | |||||||||||||||||||||||||||
| 66 | 949 | $buddySystem->usedSize->{$alloc} = $size; # Save size of allocation at offset | |||||||||||||||||||||||||||
| 67 | 949 | $buddySystem->freeChains->[$_]{$alloc + (1<<$_)}++ for $size..$F-1; # Return excess space to lower chains | |||||||||||||||||||||||||||
| 68 | 949 | return $alloc; # Return allocation | |||||||||||||||||||||||||||
| 69 | } | ||||||||||||||||||||||||||||
| 70 | } | ||||||||||||||||||||||||||||
| 71 | } | ||||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||
| 73 | # No space on any free chain - start a new chain to hold the allocation | ||||||||||||||||||||||||||||
| 74 | 92 | my $s = $buddySystem->size; # Size less than current allocation | |||||||||||||||||||||||||||
| 75 | 92 | ▶ | if ($size < $s-1) | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 76 | 45 | {my $F = $buddySystem->freeChains->[$s] = {}; # Create new chain | |||||||||||||||||||||||||||
| 77 | 45 | my $alloc = (1<<($s-1)); # Allocation address | |||||||||||||||||||||||||||
| 78 | 45 | $buddySystem->usedSize->{$alloc} = $size; # Allocation size | |||||||||||||||||||||||||||
| 79 | 45 | $buddySystem->freeChains->[$_]{$alloc + (1<<$_)}++ for $size..$s-2; # Spread excess space across lower chains | |||||||||||||||||||||||||||
| 80 | 45 | return $alloc | |||||||||||||||||||||||||||
| 81 | } | ||||||||||||||||||||||||||||
| 82 | else # Size greater than or equal to current allocation | ||||||||||||||||||||||||||||
| 83 | 47 | {my $F = $buddySystem->freeChains->[$size+1] = {}; # Create new chain | |||||||||||||||||||||||||||
| 84 | 47 | my $alloc = (1<<$size); # Allocation address | |||||||||||||||||||||||||||
| 85 | 47 | $buddySystem->usedSize->{$alloc} = $size; # Allocation size | |||||||||||||||||||||||||||
| 86 | 47 | for($s..$size) # Spread excess space across lower chains | |||||||||||||||||||||||||||
| 87 | 51 | {my $i = $size-($_+1-$s); | |||||||||||||||||||||||||||
| 88 | 51 | $buddySystem->freeChains->[$i]{(1<<$i)}++; | |||||||||||||||||||||||||||
| 89 | } | ||||||||||||||||||||||||||||
| 90 | 47 | return $alloc # Return allocation | |||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | } # alloc | ||||||||||||||||||||||||||||
| 93 | |||||||||||||||||||||||||||||
| 94 | sub locateAddress($$) # Find the current location of a block by its original address after it has been copied to a new buddy system | ||||||||||||||||||||||||||||
| 95 | 9 | ▶ | {my ($buddySystem, $alloc) = @_; # Buddy system, address at which the block was originally located | ||||||||||||||||||||||||||
|
Subroutine
locateAddress: called CC=2 SCAR=8.1
Pod
documented
| |||||||||||||||||||||||||||||
| 96 | 9 | ▶ | $buddySystem->wentTo->{$alloc} // $alloc # The relocated address if there is one, else the current address | ||||||||||||||||||||||||||
|
Condition33%1/3
$buddySystem->wentTo->{$alloc} // $alloc
MC/DC0%0/2
$buddySystem->wentTo->{$alloc} // $alloc
$buddySystem->wentTo->{$alloc}
$alloc
Truth table33%1/3
A // B
A= $buddySystem->wentTo->{$alloc}B= $alloc
| |||||||||||||||||||||||||||||
| 97 | } # locateAddress | ||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||
| 99 | sub locateName($$) # Find the current location of a named block after it has been copied to a new buddy system | ||||||||||||||||||||||||||||
| 100 | 9 | ▶ | {my ($buddySystem, $name) = @_; # Buddy system, name of the block | ||||||||||||||||||||||||||
|
Subroutine
locateName: called CC=2 SCAR=7.0
Pod
documented
| |||||||||||||||||||||||||||||
| 101 | 9 | my $alloc = $buddySystem->nameAlloc->{$name}; # Address of named block | |||||||||||||||||||||||||||
| 102 | 9 | ▶ | defined($alloc) or confess "No such named block: $name"; # Complain of no such block exists | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 103 | 9 | $buddySystem->locateAddress($alloc) # The relocated address if there is one, else the current address | |||||||||||||||||||||||||||
| 104 | } # locateName | ||||||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||||||
| 106 | sub sizeAddress($$) # Size of allocation at an address | ||||||||||||||||||||||||||||
| 107 | 9 | ▶ | {my ($buddySystem, $address) = @_; # Buddy system, address of allocation whiose size we want | ||||||||||||||||||||||||||
|
Subroutine
sizeAddress: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 108 | 9 | $buddySystem->{usedSize}{$address} # Size of allocation at specified address | |||||||||||||||||||||||||||
| 109 | } # sizeAddress | ||||||||||||||||||||||||||||
| 110 | |||||||||||||||||||||||||||||
| 111 | sub sizeName($$) # Size of a named allocation | ||||||||||||||||||||||||||||
| 112 | 9 | ▶ | {my ($buddySystem, $name) = @_; # Buddy system, address of allocation whiose size we want | ||||||||||||||||||||||||||
|
Subroutine
sizeName: called CC=2 SCAR=7.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 113 | 9 | my $address = $buddySystem->locateName($name); # Address of allocation | |||||||||||||||||||||||||||
| 114 | 9 | ▶ | defined($address) or confess "No allocation with name $name"; # Check allocation by this name exists | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 115 | 9 | $buddySystem->sizeAddress($address) # Size of named allocation | |||||||||||||||||||||||||||
| 116 | } # sizeName | ||||||||||||||||||||||||||||
| 117 | |||||||||||||||||||||||||||||
| 118 | sub freeName($$) # Free an allocated block via its name | ||||||||||||||||||||||||||||
| 119 | 0 | ▶ | {my ($buddySystem, $name) = @_; # Buddy system, name used to allocate block | ||||||||||||||||||||||||||
|
Subroutine
freeName: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 120 | 0 | my $alloc = $buddySystem->locateName($name); # Current address of named block | |||||||||||||||||||||||||||
| 121 | 0 | delete $buddySystem->nameAlloc->{$name}; # Disassociate name from block | |||||||||||||||||||||||||||
| 122 | 0 | $buddySystem->free($alloc); # Free block by address | |||||||||||||||||||||||||||
| 123 | } # freeName | ||||||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||||||
| 125 | sub free($$) # Free an allocation via its original allocation address | ||||||||||||||||||||||||||||
| 126 | 965 | ▶ | {my ($buddySystem, $alloc) = @_; # Buddy system, original allocation address | ||||||||||||||||||||||||||
|
Subroutine
free: called CC=10 SCAR=23.1
Pod
documented
| |||||||||||||||||||||||||||||
| 127 | 965 | my $s = delete $buddySystem->usedSize->{$alloc}; # Size of allocation at this alloc | |||||||||||||||||||||||||||
| 128 | 965 | ▶ | return 0 unless defined($s); # No allocation present and so no free is possible | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 129 | 965 | $buddySystem->allFrees->[$s]--; # Count allocations and frees on this chain - free always works beyond this point | |||||||||||||||||||||||||||
| 130 | |||||||||||||||||||||||||||||
| 131 | 965 | delete $buddySystem->usedSize->{$alloc}; # Remove information appertaining to this block | |||||||||||||||||||||||||||
| 132 | 965 | delete $buddySystem->wentTo->{$alloc}; | |||||||||||||||||||||||||||
| 133 | 965 | delete $buddySystem->cameFrom->{$alloc}; | |||||||||||||||||||||||||||
| 134 | |||||||||||||||||||||||||||||
| 135 | 965 | my $S = $buddySystem->size-1; # Freeing will not make the system larger | |||||||||||||||||||||||||||
| 136 | 965 | for my $c($s..$S) # Merge buddies | |||||||||||||||||||||||||||
| 137 | 1840 | {my $f = $buddySystem->freeChains->[$c]; # Free chain involved | |||||||||||||||||||||||||||
| 138 | 1840 | my $C = (1<<($c+1)); # Modulus to get upper or lower buddy of a pair | |||||||||||||||||||||||||||
| 139 | 1840 | my $u = $alloc % $C; # True if this the upper block of a buddy pair | |||||||||||||||||||||||||||
| 140 | 1840 | ▶ | my $b = $alloc + ($u ? -$C : +$C) / 2; # Locate possible buddy | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 141 | 1840 | ▶ | if (delete $buddySystem->freeChains->[$c]{$b}) # Remove buddy if it exists | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 142 | 875 | ▶ | {$alloc = $u ? $b : $alloc; # New block to place on next free chain | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 143 | } | ||||||||||||||||||||||||||||
| 144 | elsif ($c < $S) | ||||||||||||||||||||||||||||
| 145 | 919 | {$buddySystem->freeChains->[$c]{$alloc}++; # Place this unpaired block on free chain | |||||||||||||||||||||||||||
| 146 | 919 | return 1; # Finished successfully - no block merges | |||||||||||||||||||||||||||
| 147 | } | ||||||||||||||||||||||||||||
| 148 | else # Remove excess free chains | ||||||||||||||||||||||||||||
| 149 | 46 | {my $c = $buddySystem->freeChains; | |||||||||||||||||||||||||||
| 150 | 46 | my $a = $buddySystem->allFrees; | |||||||||||||||||||||||||||
| 151 | 46 | for(1..@$c) # Remove a chain if it has nothing allocated | |||||||||||||||||||||||||||
| 152 | 306 | {my $i = @$c-$_; | |||||||||||||||||||||||||||
| 153 | 306 | ▶ | last if $a->[$i]; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 154 | 306 | ▶ | pop @$a if $i < @$a; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 155 | 306 | pop @$c; | |||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||
| 157 | 46 | return 2; # Finished successfully - one or more blocks were merged | |||||||||||||||||||||||||||
| 158 | } | ||||||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||||
| 160 | 0 | confess "This code should be unreachable" # Unreachable | |||||||||||||||||||||||||||
| 161 | } # free | ||||||||||||||||||||||||||||
| 162 | |||||||||||||||||||||||||||||
| 163 | #2 Statistics # These methods provide statistics on memory usage in the buddy system | ||||||||||||||||||||||||||||
| 164 | |||||||||||||||||||||||||||||
| 165 | sub usedSpace($) # Total allocated space in this buddy system | ||||||||||||||||||||||||||||
| 166 | 1100 | ▶ | {my ($buddySystem) = @_; # Buddy system | ||||||||||||||||||||||||||
|
Subroutine
usedSpace: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 167 | 1100 | my $n = 0; | |||||||||||||||||||||||||||
| 168 | 1100 | my $u = $buddySystem->usedSize; | |||||||||||||||||||||||||||
| 169 | 1100 | $n += (1<<$u->{$_}) for keys %$u; | |||||||||||||||||||||||||||
| 170 | 1100 | $n | |||||||||||||||||||||||||||
| 171 | } # usedSpace | ||||||||||||||||||||||||||||
| 172 | |||||||||||||||||||||||||||||
| 173 | sub freeSpace($) # Total free space that can still be allocated in this buddy system without changing its size | ||||||||||||||||||||||||||||
| 174 | 2099 | ▶ | {my ($buddySystem) = @_; # Buddy system | ||||||||||||||||||||||||||
|
Subroutine
freeSpace: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 175 | 2099 | my $n = 0; | |||||||||||||||||||||||||||
| 176 | 2099 | for(0..$buddySystem->size-1) | |||||||||||||||||||||||||||
| 177 | 32412 | {my $f = $buddySystem->freeChains->[$_]; | |||||||||||||||||||||||||||
| 178 | 32412 | ▶ | next unless $f; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 179 | 30218 | $n += scalar(keys %$f) * (1<<$_); | |||||||||||||||||||||||||||
| 180 | } | ||||||||||||||||||||||||||||
| 181 | $n | ||||||||||||||||||||||||||||
| 182 | 2099 | } # freeSpace | |||||||||||||||||||||||||||
| 183 | |||||||||||||||||||||||||||||
| 184 | sub totalSpace($) # Total space currently occupied by this buddy system | ||||||||||||||||||||||||||||
| 185 | 2371 | ▶ | {my ($buddySystem) = @_; # Buddy system | ||||||||||||||||||||||||||
|
Subroutine
totalSpace: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 186 | 2371 | my $n = $buddySystem->size; | |||||||||||||||||||||||||||
| 187 | 2371 | ▶ | return 0 unless $n; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 188 | 2291 | 1 << ($buddySystem->size-1) # System invariant | |||||||||||||||||||||||||||
| 189 | } # totalSpace | ||||||||||||||||||||||||||||
| 190 | |||||||||||||||||||||||||||||
| 191 | sub fractionalFreeSpace($) ## Fraction of space currently free vs total space | ||||||||||||||||||||||||||||
| 192 | 1015 | ▶ | {my ($buddySystem) = @_; # Buddy system | ||||||||||||||||||||||||||
|
Subroutine
fractionalFreeSpace: called CC=2 SCAR=7.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 193 | 1015 | my $t = $buddySystem->totalSpace; | |||||||||||||||||||||||||||
| 194 | 1015 | my $f = $buddySystem->freeSpace; | |||||||||||||||||||||||||||
| 195 | 1015 | ▶ | return 1 unless $t > 0; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 196 | 1015 | $f / $t | |||||||||||||||||||||||||||
| 197 | } # fractionalFreeSpace | ||||||||||||||||||||||||||||
| 198 | |||||||||||||||||||||||||||||
| 199 | sub checkSpace($) ## Check free space and used space match total space | ||||||||||||||||||||||||||||
| 200 | 1084 | ▶ | {my ($buddySystem) = @_; # Buddy system | ||||||||||||||||||||||||||
|
Subroutine
checkSpace: called CC=5 SCAR=16.2
Pod
undocumented
| |||||||||||||||||||||||||||||
| 201 | 1084 | my $b = $buddySystem; # Shorten | |||||||||||||||||||||||||||
| 202 | 1084 | my $u = $b->usedSpace; | |||||||||||||||||||||||||||
| 203 | 1084 | my $f = $b->freeSpace; | |||||||||||||||||||||||||||
| 204 | 1084 | my $t = $b->totalSpace; | |||||||||||||||||||||||||||
| 205 | 1084 | my $T = $u + $f; | |||||||||||||||||||||||||||
| 206 | 1084 | ▶ | confess "checkSpace failed used=$u free=$f used+free=$T != total=$t\n" | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 207 | # .dump($b)."\n" | ||||||||||||||||||||||||||||
| 208 | unless $u+$f == $t; | ||||||||||||||||||||||||||||
| 209 | |||||||||||||||||||||||||||||
| 210 | 1084 | if (1) # Confirm used space matches allocated space | |||||||||||||||||||||||||||
| 211 | 1084 | {my $n = 0; | |||||||||||||||||||||||||||
| 212 | 1084 | for my $s(0..$b->size-1) # All the free chains | |||||||||||||||||||||||||||
| 213 | 16287 | ▶ | {$n += ($b->allFrees->[$s]//0) * (1<<$s); # Number of currently allocated blocks of this size | ||||||||||||||||||||||||||
|
Condition100%2/2
$b->allFrees->[$s] // 0
MC/DC100%1/1
$b->allFrees->[$s] // 0
$b->allFrees->[$s]
Truth table100%2/2
A
A= $b->allFrees->[$s]
| |||||||||||||||||||||||||||||
| 214 | } | ||||||||||||||||||||||||||||
| 215 | 1084 | ▶ | confess "checkSpace failed used=$u n=$n" | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 216 | # .dump($b)."\n" | ||||||||||||||||||||||||||||
| 217 | unless $u == $n; | ||||||||||||||||||||||||||||
| 218 | } | ||||||||||||||||||||||||||||
| 219 | |||||||||||||||||||||||||||||
| 220 | 1 | ||||||||||||||||||||||||||||
| 221 | 1084 | } # checkSpace | |||||||||||||||||||||||||||
| 222 | |||||||||||||||||||||||||||||
| 223 | sub visualise($$) ## Create a pictorial representation of the buddy system with free in lowercase and used in uppercase. Confess if free and used chains are inconsistent | ||||||||||||||||||||||||||||
| 224 | 82 | ▶ | {my ($buddySystem, $title) = @_; # BuddySystem, title | ||||||||||||||||||||||||||
|
Subroutine
visualise: called CC=19 SCAR=31.5
Pod
undocumented
| |||||||||||||||||||||||||||||
| 225 | 82 | my $S = $buddySystem->size; # Size of system | |||||||||||||||||||||||||||
| 226 | 82 | my $L = 26; # Length of alphabet | |||||||||||||||||||||||||||
| 227 | 82 | my @A = map {chr(ord('a')-1+$_)} 1..$L; # Use lowercase for free areas and upper case for used areas | |||||||||||||||||||||||||||
| 228 | 82 | my $e = 0; my $x = 0; # Number of error cells, number of cells examined | |||||||||||||||||||||||||||
| 229 | |||||||||||||||||||||||||||||
| 230 | 82 | my @t = map {undef()} 1..$buddySystem->totalSpace; # Long representation | |||||||||||||||||||||||||||
| 231 | 82 | for my $B(0..$S-1) # All the free/used blocks | |||||||||||||||||||||||||||
| 232 | 543 | {my $s = (1<<$B); # Size of free blocks on this chain | |||||||||||||||||||||||||||
| 233 | 543 | ▶ | if (my $F = $buddySystem->freeChains->[$B]) # Free blocks of this size | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 234 | 223 | {for my $f(sort {$a <=> $b} keys %$F) # Free block | |||||||||||||||||||||||||||
| 235 | 100 | {for(0..$s-1) # Each cell of free block | |||||||||||||||||||||||||||
| 236 | 131634 | {my $o = $f+$_; # Offset | |||||||||||||||||||||||||||
| 237 | 131634 | my $c = $A[$B % $L]; # Marker character for free block | |||||||||||||||||||||||||||
| 238 | 131634 | ++$x; # Examined cells count | |||||||||||||||||||||||||||
| 239 | 0 | ▶ | if (defined($t[$o])) {++$e; $t[$o] = '*'} else {$t[$o] = $c} # Do not overwrite previous free or used block | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 240 | } | ||||||||||||||||||||||||||||
| 241 | } | ||||||||||||||||||||||||||||
| 242 | } | ||||||||||||||||||||||||||||
| 243 | } | ||||||||||||||||||||||||||||
| 244 | 82 | ▶ | if (my $U = $buddySystem->usedSize) # Used blocks | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 245 | 82 | {for my $u(sort {$a <=> $b} keys %$U) # Used blocks in ascending order of offset | |||||||||||||||||||||||||||
| 246 | 216 | {my $s = $U->{$u}; # Size of this used block | |||||||||||||||||||||||||||
| 247 | 216 | for(1..(1<<$s)) # Each cell of used block | |||||||||||||||||||||||||||
| 248 | 18847 | {my $o = $u+$_-1; # Offset | |||||||||||||||||||||||||||
| 249 | 18847 | my $c = $A[$s % $L]; # Marker character for used block | |||||||||||||||||||||||||||
| 250 | 18847 | ++$x; | |||||||||||||||||||||||||||
| 251 | 0 | ▶ | if (defined($t[$o])) {++$e; $t[$o] = '*'} else {$t[$o] = uc $c} # Do not overwrite previous free or used block | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 252 | } | ||||||||||||||||||||||||||||
| 253 | } | ||||||||||||||||||||||||||||
| 254 | } | ||||||||||||||||||||||||||||
| 255 | 82 | ▶ | if ($e or $x != $buddySystem->totalSpace) # Inconsistent state detected | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$e or $x != $buddySystem->totalSpace
MC/DC0%0/2
$e or $x != $buddySystem->totalSpace
$e
$x != $buddySystem->totalSpace
Truth table33%1/3
A or B
A= $eB= $x != $buddySystem->totalSpace
| |||||||||||||||||||||||||||||
| 256 | 1 | ▶ | {use Data::Dump qw(dump); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 257 | 1 | ▶ | use Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 258 | 0 | say STDOUT "Inconsistent State!"; | |||||||||||||||||||||||||||
| 259 | 0 | say STDOUT " e=$e x=$x length=", $buddySystem->totalSpace; | |||||||||||||||||||||||||||
| 260 | 0 | say STDOUT " ", dump($buddySystem); | |||||||||||||||||||||||||||
| 261 | 0 | ▶ | say STDOUT '=', join '', map {$_//'*'} @t, "="; | ||||||||||||||||||||||||||
|
Condition0%0/2
$_ // "*"
MC/DC0%0/1
$_ // "*"
$_
Truth table0%0/2
A
A= $_
| |||||||||||||||||||||||||||||
| 262 | 0 | confess "Inconsistent state"; | |||||||||||||||||||||||||||
| 263 | } | ||||||||||||||||||||||||||||
| 264 | |||||||||||||||||||||||||||||
| 265 | 82 | my @T = map {''} 1..$buddySystem->totalSpace; # Short representation | |||||||||||||||||||||||||||
| 266 | 82 | for my $B(0..$S-1) # All the free/used blocks | |||||||||||||||||||||||||||
| 267 | 543 | {my $s = (1<<$B); # Size of free blocks on this chain | |||||||||||||||||||||||||||
| 268 | 543 | ▶ | if (my $F = $buddySystem->freeChains->[$B]) # Free blocks of this size | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 269 | 223 | {$T[$_] = $A[$B % $L] for sort {$a <=> $b} keys %$F; # Free block | |||||||||||||||||||||||||||
| 270 | } | ||||||||||||||||||||||||||||
| 271 | } | ||||||||||||||||||||||||||||
| 272 | 82 | ▶ | if (my $U = $buddySystem->usedSize) # Used blocks | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 273 | 82 | {for my $u(sort {$a <=> $b} keys %$U) # Used blocks in ascending order of offset | |||||||||||||||||||||||||||
| 274 | 216 | {my $s = $U->{$u}; # Size of this used block | |||||||||||||||||||||||||||
| 275 | 216 | $T[$u] = uc $A[$s % $L]; | |||||||||||||||||||||||||||
| 276 | } | ||||||||||||||||||||||||||||
| 277 | } | ||||||||||||||||||||||||||||
| 278 | 82 | my $T = join '', @T; # Representation as a string | |||||||||||||||||||||||||||
| 279 | 82 | ▶ | say STDOUT "$title $T" if $title; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 280 | 82 | $T | |||||||||||||||||||||||||||
| 281 | } # visualise | ||||||||||||||||||||||||||||
| 282 | |||||||||||||||||||||||||||||
| 283 | #2 Relocation # These methods copy one buddy system to another compacting free space in the process. | ||||||||||||||||||||||||||||
| 284 | sub copy($$;$) # Copy a buddy system to compact its free space, the largest blocks are placed in (0) - ascending, (1) - descending order of size, blocks that get relocated to new positions in the new buddy system will still be accessible by their original address or name | ||||||||||||||||||||||||||||
| 285 | 2 | ▶ | {my ($buddySystem, $order, $copy) = @_; # Buddy system, order, optional copy method to copy an old allocation into its corresponding new allocation | ||||||||||||||||||||||||||
|
Subroutine
copy: called CC=9 SCAR=23.2
Pod
documented
| |||||||||||||||||||||||||||||
| 286 | 2 | my $n = new; # The new buddy system | |||||||||||||||||||||||||||
| 287 | |||||||||||||||||||||||||||||
| 288 | 2 | ▶ | if (my $u = $buddySystem->usedSize) # Used blocks decreasing in size but increasing by address within each size | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 289 | {my @u = sort | ||||||||||||||||||||||||||||
| 290 | 2 | ▶ | {my $c = $order ? $u->{$b} <=> $u->{$a} : $u->{$a} <=> $u->{$b}; # 0 - Ascending, 1 - Descending order | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 291 | 73 | ▶ | return $c unless $c == 0; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 292 | 14 | $a <=> $b # Ascending address | |||||||||||||||||||||||||||
| 293 | } keys %$u; | ||||||||||||||||||||||||||||
| 294 | |||||||||||||||||||||||||||||
| 295 | 2 | for my $a(@u) # Each used block | |||||||||||||||||||||||||||
| 296 | 26 | {my $size = $u->{$a}; # Size of this block | |||||||||||||||||||||||||||
| 297 | 26 | my $A; # Address of relocated block | |||||||||||||||||||||||||||
| 298 | 26 | ▶ | if (my $name = $buddySystem->allocName->{$a}) # Name attached to the block | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 299 | 9 | {$A = $n->allocField($name, $size); # Create new block with same name in new buddy system | |||||||||||||||||||||||||||
| 300 | } | ||||||||||||||||||||||||||||
| 301 | else | ||||||||||||||||||||||||||||
| 302 | 17 | {$A = $n->alloc($size); # Matching block in new buddy system | |||||||||||||||||||||||||||
| 303 | } | ||||||||||||||||||||||||||||
| 304 | 26 | ▶ | $copy->($a, $A, $size) if $copy; # Copy data from old block to new block, using the specified size | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 305 | 26 | ▶ | if (my $f = $buddySystem->cameFrom->{$a}) # Address this block originally came from if different from new address | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 306 | 0 | ▶ | {if ($f != $A) # Record new position if different | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 307 | 0 | {$n->cameFrom->{$A} = $f; # The original address at which the block was allocated | |||||||||||||||||||||||||||
| 308 | 0 | $n->wentTo ->{$f} = $A; # The current address of a block from its original address | |||||||||||||||||||||||||||
| 309 | } | ||||||||||||||||||||||||||||
| 310 | } | ||||||||||||||||||||||||||||
| 311 | } | ||||||||||||||||||||||||||||
| 312 | } | ||||||||||||||||||||||||||||
| 313 | $n | ||||||||||||||||||||||||||||
| 314 | 2 | } # copy | |||||||||||||||||||||||||||
| 315 | |||||||||||||||||||||||||||||
| 316 | sub copyLargestLast($;$) # Copy a buddy system, compacting free space, the new addresses of allocations can be found in wentTo, the largest blocks are placed last | ||||||||||||||||||||||||||||
| 317 | 1 | ▶ | {my ($buddySystem, $copy) = @_; # BuddySystem, copy method to copy an old allocation into a new allocation | ||||||||||||||||||||||||||
|
Subroutine
copyLargestLast: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 318 | 1 | copy($buddySystem, 0, $copy); # Copy the buddy system | |||||||||||||||||||||||||||
| 319 | } # copyLargestLast | ||||||||||||||||||||||||||||
| 320 | |||||||||||||||||||||||||||||
| 321 | sub copyLargestFirst($;$) # Copy a buddy system, compacting free space, the new addresses of allocations can be found in wentTo, the largest blocks are placed first | ||||||||||||||||||||||||||||
| 322 | 1 | ▶ | {my ($buddySystem, $copy) = @_; # BuddySystem, copy method to copy an old allocation into a new allocation | ||||||||||||||||||||||||||
|
Subroutine
copyLargestFirst: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 323 | 1 | copy($buddySystem, 1, $copy); # Copy the buddy system | |||||||||||||||||||||||||||
| 324 | } # copyLargestFirst | ||||||||||||||||||||||||||||
| 325 | |||||||||||||||||||||||||||||
| 326 | |||||||||||||||||||||||||||||
| 327 | #2 Structure # This method generates a blessed sub whose methods provide named access to allocations backed by a L<perlfunc/vec> string | ||||||||||||||||||||||||||||
| 328 | sub generateStructureFields($$) # Return a blessed sub whose methods access the named blocks in the buddy system. The blessed sub returns a text representation of the method definitions | ||||||||||||||||||||||||||||
| 329 | 1 | ▶ | {my ($buddySystem, $package) = @_; # Buddy system, structure name | ||||||||||||||||||||||||||
|
Subroutine
generateStructureFields: called CC=5 SCAR=16.2
Pod
documented
| |||||||||||||||||||||||||||||
| 330 | 1 | my $new = $buddySystem->copyLargestLast; # Organise the buddy system by element size | |||||||||||||||||||||||||||
| 331 | 1 | my %allocs = %{$new->allocName}; # Named allocations | |||||||||||||||||||||||||||
| 332 | 1 | my %sizes = %{$new->usedSize}; # Size of each named allocation | |||||||||||||||||||||||||||
| 333 | 1 | my $s = <<END; # String of sub definitions in the specified package | |||||||||||||||||||||||||||
| 334 | package $package; | ||||||||||||||||||||||||||||
| 335 | use utf8; | ||||||||||||||||||||||||||||
| 336 | END | ||||||||||||||||||||||||||||
| 337 | 1 | my @s; | |||||||||||||||||||||||||||
| 338 | 1 | for my $alloc(sort {$a<=>$b} keys %allocs) | |||||||||||||||||||||||||||
| 339 | 9 | {my $name = $allocs{$alloc}; # Name of block | |||||||||||||||||||||||||||
| 340 | 9 | my $size = $sizes{$alloc}; # Log2 width of block | |||||||||||||||||||||||||||
| 341 | 9 | my $bits = 2**$size; # Block size in vec terms | |||||||||||||||||||||||||||
| 342 | 9 | my $offset = $alloc/$bits; # Block offset in vec terms | |||||||||||||||||||||||||||
| 343 | 9 | ▶ | $offset == int($offset) or # Something has gone seriously wrong if this calculation fails to produce an integer | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 344 | confess "Offset should be an integer not $offset"; | ||||||||||||||||||||||||||||
| 345 | 9 | push @s, # Generate an lvalue sub to access the block by the assigned name | |||||||||||||||||||||||||||
| 346 | ["sub $name", " :lvalue {vec(\$_[1], ", $offset.", ", $bits, ")}\n"]; | ||||||||||||||||||||||||||||
| 347 | } | ||||||||||||||||||||||||||||
| 348 | 1 | $s .= formatTableBasic([@s]); # Layout the method definitions so they are easy to read | |||||||||||||||||||||||||||
| 349 | 0 | ▶ | eval $s; # Generate methods | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
Subroutine
𝝖: called CC=1 SCAR=0.0
Subroutine
𝝗: called CC=1 SCAR=0.0
Subroutine
𝝙: not called CC=1 SCAR=0.0
Subroutine
𝝰: called CC=1 SCAR=0.0
Subroutine
𝝱: called CC=1 SCAR=0.0
Subroutine
𝝲: called CC=1 SCAR=0.0
Subroutine
𝝳: not called CC=1 SCAR=0.0
Subroutine
𝝺: called CC=1 SCAR=0.0
Subroutine
𝞈: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 350 | 1 | ▶ | $@ and confess "$s\n$@"; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 351 | 1 | my $p = <<END; # Define the blessed sub whose value is the text representation if its methods | |||||||||||||||||||||||||||
| 352 | bless sub {\$s}, "$package"; | ||||||||||||||||||||||||||||
| 353 | END | ||||||||||||||||||||||||||||
| 354 | 1 | my $P = eval $p; # Generate the blessed sub whose value is the text representation if its methods | |||||||||||||||||||||||||||
| 355 | 1 | ▶ | $@ and confess "$p\n$@"; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 356 | 1 | $P | |||||||||||||||||||||||||||
| 357 | } # generateStructureFields | ||||||||||||||||||||||||||||
| 358 | |||||||||||||||||||||||||||||
| 359 | # Test | ||||||||||||||||||||||||||||
| 360 | 1 | ▶ | sub test{eval join('', <Data::Layout::BuddySystem::DATA>) or die $@} | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
Subroutine
BEGIN: called CC=1 SCAR=0.0
Subroutine
test: called CC=2 SCAR=7.0
Pod
undocumented
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 361 | |||||||||||||||||||||||||||||
| 362 | 1 | ▶ | test unless caller; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 363 | |||||||||||||||||||||||||||||
| 364 | # Documentation | ||||||||||||||||||||||||||||
| 365 | #extractDocumentation() unless caller; # Extract the documentation | ||||||||||||||||||||||||||||
| 366 | |||||||||||||||||||||||||||||
| 367 | 1 | 1; | |||||||||||||||||||||||||||
| 368 | |||||||||||||||||||||||||||||
| 369 | =encoding utf-8 | ||||||||||||||||||||||||||||
| 370 | |||||||||||||||||||||||||||||
| 371 | =head1 Name | ||||||||||||||||||||||||||||
| 372 | |||||||||||||||||||||||||||||
| 373 | Data::Layout::BuddySystem - Layout data in memory allocated via a buddy system | ||||||||||||||||||||||||||||
| 374 | |||||||||||||||||||||||||||||
| 375 | =head1 Synopsis | ||||||||||||||||||||||||||||
| 376 | |||||||||||||||||||||||||||||
| 377 | use Test::More tests=>10; | ||||||||||||||||||||||||||||
| 378 | use Data::Layout::BuddySystem; | ||||||||||||||||||||||||||||
| 379 | use utf8; | ||||||||||||||||||||||||||||
| 380 | |||||||||||||||||||||||||||||
| 381 | my $b = Data::Layout::BuddySystem::new; # Create a new buddy system | ||||||||||||||||||||||||||||
| 382 | |||||||||||||||||||||||||||||
| 383 | $b->allocField(@$_) for # Allocate fields in the buddy system | ||||||||||||||||||||||||||||
| 384 | [𝝳=>6], [𝝰=>0], [𝝙=>6],[𝝱=>0],[𝞈 =>4], [𝝺=>5], [𝝲=>0], [𝝖=>3], [𝝗=>3]; # Name and log2 size of each field | ||||||||||||||||||||||||||||
| 385 | |||||||||||||||||||||||||||||
| 386 | my $s = $b->generateStructureFields('Struct'); # Generate structure definition | ||||||||||||||||||||||||||||
| 387 | |||||||||||||||||||||||||||||
| 388 | ok nws($s->()) eq nws(<<'END'); # String representation of methods associated with generated structure | ||||||||||||||||||||||||||||
| 389 | package Struct; | ||||||||||||||||||||||||||||
| 390 | use utf8; | ||||||||||||||||||||||||||||
| 391 | sub 𝝰 :lvalue {vec($_[1], 0, 1 )} | ||||||||||||||||||||||||||||
| 392 | sub 𝝱 :lvalue {vec($_[1], 1, 1 )} | ||||||||||||||||||||||||||||
| 393 | sub 𝝲 :lvalue {vec($_[1], 2, 1 )} | ||||||||||||||||||||||||||||
| 394 | sub 𝝖 :lvalue {vec($_[1], 1, 8 )} | ||||||||||||||||||||||||||||
| 395 | sub 𝝗 :lvalue {vec($_[1], 2, 8 )} | ||||||||||||||||||||||||||||
| 396 | sub 𝞈 :lvalue {vec($_[1], 2, 16 )} | ||||||||||||||||||||||||||||
| 397 | sub 𝝺 :lvalue {vec($_[1], 2, 32 )} | ||||||||||||||||||||||||||||
| 398 | sub 𝝳 :lvalue {vec($_[1], 2, 64 )} | ||||||||||||||||||||||||||||
| 399 | sub 𝝙 :lvalue {vec($_[1], 3, 64 )} | ||||||||||||||||||||||||||||
| 400 | END | ||||||||||||||||||||||||||||
| 401 | |||||||||||||||||||||||||||||
| 402 | if (1) # Set fields | ||||||||||||||||||||||||||||
| 403 | {$s->𝝰(my $𝕄) = 1; ok $𝕄 eq "\1"; | ||||||||||||||||||||||||||||
| 404 | $s->𝝱( $𝕄) = 0; ok $𝕄 eq "\1"; | ||||||||||||||||||||||||||||
| 405 | $s->𝝲( $𝕄) = 1; ok $𝕄 eq "\5"; | ||||||||||||||||||||||||||||
| 406 | $s->𝝖( $𝕄) = 3; ok $𝕄 eq "\x05\x03"; # Byte fields | ||||||||||||||||||||||||||||
| 407 | $s->𝝗( $𝕄) = 7; ok $𝕄 eq "\x05\x03\x07"; | ||||||||||||||||||||||||||||
| 408 | $s->𝞈( $𝕄) = 9; ok $𝕄 eq "\x05\x03\x07\x00\x00\x09"; # Word field | ||||||||||||||||||||||||||||
| 409 | } | ||||||||||||||||||||||||||||
| 410 | |||||||||||||||||||||||||||||
| 411 | if (1) # Set and get an integer field | ||||||||||||||||||||||||||||
| 412 | {$s->𝝺(my $𝕄) = 2; ok $s->𝝺($𝕄) == 2; # Set field | ||||||||||||||||||||||||||||
| 413 | $s->𝝺( $𝕄)++; ok $s->𝝺($𝕄) == 3; # Increment field | ||||||||||||||||||||||||||||
| 414 | ok $𝕄 eq "\0\0\0\0\0\0\0\0\0\0\0\3"; # Dump the memory organised by the buddy system | ||||||||||||||||||||||||||||
| 415 | } | ||||||||||||||||||||||||||||
| 416 | |||||||||||||||||||||||||||||
| 417 | =head1 Description | ||||||||||||||||||||||||||||
| 418 | |||||||||||||||||||||||||||||
| 419 | Implements the buddy system described at L<https://en.wikipedia.org/wiki/Buddy_memory_allocation> | ||||||||||||||||||||||||||||
| 420 | in 100% Pure Perl. Blocks can be identified by names or addresses which remain | ||||||||||||||||||||||||||||
| 421 | invariant even after one buddy system has been copied to a new one to compact | ||||||||||||||||||||||||||||
| 422 | free space. Each named allocation can be accessed via a generated method which | ||||||||||||||||||||||||||||
| 423 | identifies an lvalue area of a L<perlfunc/vec> string used to back the memory | ||||||||||||||||||||||||||||
| 424 | organised by the buddy system. | ||||||||||||||||||||||||||||
| 425 | |||||||||||||||||||||||||||||
| 426 | |||||||||||||||||||||||||||||
| 427 | =head1 Methods | ||||||||||||||||||||||||||||
| 428 | |||||||||||||||||||||||||||||
| 429 | =head2 new() | ||||||||||||||||||||||||||||
| 430 | |||||||||||||||||||||||||||||
| 431 | Create a new Buddy system | ||||||||||||||||||||||||||||
| 432 | |||||||||||||||||||||||||||||
| 433 | |||||||||||||||||||||||||||||
| 434 | =head2 allocField($buddySystem, $name, $size) | ||||||||||||||||||||||||||||
| 435 | |||||||||||||||||||||||||||||
| 436 | Allocate a block in the buddy system, give it a name that is invariant even after this buddy system has been copied to a new buddy system to compact its storage, and return the address of its location in the buddy system | ||||||||||||||||||||||||||||
| 437 | |||||||||||||||||||||||||||||
| 438 | Parameter Description | ||||||||||||||||||||||||||||
| 439 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 440 | 2 $name name of block | ||||||||||||||||||||||||||||
| 441 | 3 $size integer log2(size of allocation) | ||||||||||||||||||||||||||||
| 442 | |||||||||||||||||||||||||||||
| 443 | =head2 alloc($buddySystem, $size) | ||||||||||||||||||||||||||||
| 444 | |||||||||||||||||||||||||||||
| 445 | Allocate a block and return its address | ||||||||||||||||||||||||||||
| 446 | |||||||||||||||||||||||||||||
| 447 | Parameter Description | ||||||||||||||||||||||||||||
| 448 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 449 | 2 $size integer log2(size of allocation) | ||||||||||||||||||||||||||||
| 450 | |||||||||||||||||||||||||||||
| 451 | =head2 locateAddress($buddySystem, $alloc) | ||||||||||||||||||||||||||||
| 452 | |||||||||||||||||||||||||||||
| 453 | Find the current location of a block by its original address after it has been copied to a new buddy system | ||||||||||||||||||||||||||||
| 454 | |||||||||||||||||||||||||||||
| 455 | Parameter Description | ||||||||||||||||||||||||||||
| 456 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 457 | 2 $alloc address at which the block was originally located | ||||||||||||||||||||||||||||
| 458 | |||||||||||||||||||||||||||||
| 459 | =head2 locateName($buddySystem, $name) | ||||||||||||||||||||||||||||
| 460 | |||||||||||||||||||||||||||||
| 461 | Find the current location of a named block after it has been copied to a new buddy system | ||||||||||||||||||||||||||||
| 462 | |||||||||||||||||||||||||||||
| 463 | Parameter Description | ||||||||||||||||||||||||||||
| 464 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 465 | 2 $name name of the block | ||||||||||||||||||||||||||||
| 466 | |||||||||||||||||||||||||||||
| 467 | =head2 freeName($buddySystem, $name) | ||||||||||||||||||||||||||||
| 468 | |||||||||||||||||||||||||||||
| 469 | Free an allocated block via its name | ||||||||||||||||||||||||||||
| 470 | |||||||||||||||||||||||||||||
| 471 | Parameter Description | ||||||||||||||||||||||||||||
| 472 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 473 | 2 $name name used to allocate block | ||||||||||||||||||||||||||||
| 474 | |||||||||||||||||||||||||||||
| 475 | =head2 free($buddySystem, $alloc) | ||||||||||||||||||||||||||||
| 476 | |||||||||||||||||||||||||||||
| 477 | Free an allocation via its original allocation address | ||||||||||||||||||||||||||||
| 478 | |||||||||||||||||||||||||||||
| 479 | Parameter Description | ||||||||||||||||||||||||||||
| 480 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 481 | 2 $alloc original allocation address | ||||||||||||||||||||||||||||
| 482 | |||||||||||||||||||||||||||||
| 483 | =head2 Statistics | ||||||||||||||||||||||||||||
| 484 | |||||||||||||||||||||||||||||
| 485 | These methods provide statistics on memory usage in the buddy system | ||||||||||||||||||||||||||||
| 486 | |||||||||||||||||||||||||||||
| 487 | =head3 usedSpace($buddySystem) | ||||||||||||||||||||||||||||
| 488 | |||||||||||||||||||||||||||||
| 489 | Total allocated space in this buddy system | ||||||||||||||||||||||||||||
| 490 | |||||||||||||||||||||||||||||
| 491 | Parameter Description | ||||||||||||||||||||||||||||
| 492 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 493 | |||||||||||||||||||||||||||||
| 494 | =head3 freeSpace($buddySystem) | ||||||||||||||||||||||||||||
| 495 | |||||||||||||||||||||||||||||
| 496 | Total free space that can still be allocated in this buddy system without changing its size | ||||||||||||||||||||||||||||
| 497 | |||||||||||||||||||||||||||||
| 498 | Parameter Description | ||||||||||||||||||||||||||||
| 499 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 500 | |||||||||||||||||||||||||||||
| 501 | =head3 totalSpace($buddySystem) | ||||||||||||||||||||||||||||
| 502 | |||||||||||||||||||||||||||||
| 503 | Total space currently occupied by this buddy system | ||||||||||||||||||||||||||||
| 504 | |||||||||||||||||||||||||||||
| 505 | Parameter Description | ||||||||||||||||||||||||||||
| 506 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 507 | |||||||||||||||||||||||||||||
| 508 | =head2 Relocation | ||||||||||||||||||||||||||||
| 509 | |||||||||||||||||||||||||||||
| 510 | These methods copy one buddy system to another compacting free space in the process. | ||||||||||||||||||||||||||||
| 511 | |||||||||||||||||||||||||||||
| 512 | =head3 copy($buddySystem, $order, $copy) | ||||||||||||||||||||||||||||
| 513 | |||||||||||||||||||||||||||||
| 514 | Copy a buddy system to compact its free space, the largest blocks are placed in (0) - ascending, (1) - descending order of size, blocks that get relocated to new positions in the new buddy system will still be accessible by their original address or name | ||||||||||||||||||||||||||||
| 515 | |||||||||||||||||||||||||||||
| 516 | Parameter Description | ||||||||||||||||||||||||||||
| 517 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 518 | 2 $order order | ||||||||||||||||||||||||||||
| 519 | 3 $copy optional copy method to copy an old allocation into its corresponding new allocation | ||||||||||||||||||||||||||||
| 520 | |||||||||||||||||||||||||||||
| 521 | =head3 copyLargestLast($buddySystem, $copy) | ||||||||||||||||||||||||||||
| 522 | |||||||||||||||||||||||||||||
| 523 | Copy a buddy system, compacting free space, the new addresses of allocations can be found in wentTo, the largest blocks are placed last | ||||||||||||||||||||||||||||
| 524 | |||||||||||||||||||||||||||||
| 525 | Parameter Description | ||||||||||||||||||||||||||||
| 526 | 1 $buddySystem BuddySystem | ||||||||||||||||||||||||||||
| 527 | 2 $copy copy method to copy an old allocation into a new allocation | ||||||||||||||||||||||||||||
| 528 | |||||||||||||||||||||||||||||
| 529 | =head3 copyLargestFirst($buddySystem, $copy) | ||||||||||||||||||||||||||||
| 530 | |||||||||||||||||||||||||||||
| 531 | Copy a buddy system, compacting free space, the new addresses of allocations can be found in wentTo, the largest blocks are placed first | ||||||||||||||||||||||||||||
| 532 | |||||||||||||||||||||||||||||
| 533 | Parameter Description | ||||||||||||||||||||||||||||
| 534 | 1 $buddySystem BuddySystem | ||||||||||||||||||||||||||||
| 535 | 2 $copy copy method to copy an old allocation into a new allocation | ||||||||||||||||||||||||||||
| 536 | |||||||||||||||||||||||||||||
| 537 | =head2 Structure | ||||||||||||||||||||||||||||
| 538 | |||||||||||||||||||||||||||||
| 539 | This method generates a blessed sub whose methods provide named access to allocations backed by a L<perlfunc/vec> string | ||||||||||||||||||||||||||||
| 540 | |||||||||||||||||||||||||||||
| 541 | =head3 generateStructureFields($buddySystem, $package) | ||||||||||||||||||||||||||||
| 542 | |||||||||||||||||||||||||||||
| 543 | Return a blessed sub whose methods access the named blocks in the buddy system. The blessed sub returns a text representation of the method definitions | ||||||||||||||||||||||||||||
| 544 | |||||||||||||||||||||||||||||
| 545 | Parameter Description | ||||||||||||||||||||||||||||
| 546 | 1 $buddySystem Buddy system | ||||||||||||||||||||||||||||
| 547 | 2 $package structure name | ||||||||||||||||||||||||||||
| 548 | |||||||||||||||||||||||||||||
| 549 | =head1 Index | ||||||||||||||||||||||||||||
| 550 | |||||||||||||||||||||||||||||
| 551 | The following methods will be exported by the :all tag | ||||||||||||||||||||||||||||
| 552 | |||||||||||||||||||||||||||||
| 553 | L</alloc($buddySystem, $size)> | ||||||||||||||||||||||||||||
| 554 | L</allocField($buddySystem, $name, $size)> | ||||||||||||||||||||||||||||
| 555 | L</copy($buddySystem, $order, $copy)> | ||||||||||||||||||||||||||||
| 556 | L</copyLargestFirst($buddySystem, $copy)> | ||||||||||||||||||||||||||||
| 557 | L</copyLargestLast($buddySystem, $copy)> | ||||||||||||||||||||||||||||
| 558 | L</free($buddySystem, $alloc)> | ||||||||||||||||||||||||||||
| 559 | L</freeName($buddySystem, $name)> | ||||||||||||||||||||||||||||
| 560 | L</freeSpace($buddySystem)> | ||||||||||||||||||||||||||||
| 561 | L</generateStructureFields($buddySystem, $package)> | ||||||||||||||||||||||||||||
| 562 | L</locateAddress($buddySystem, $alloc)> | ||||||||||||||||||||||||||||
| 563 | L</locateName($buddySystem, $name)> | ||||||||||||||||||||||||||||
| 564 | L</new()> | ||||||||||||||||||||||||||||
| 565 | L</totalSpace($buddySystem)> | ||||||||||||||||||||||||||||
| 566 | L</usedSpace($buddySystem)> | ||||||||||||||||||||||||||||
| 567 | |||||||||||||||||||||||||||||
| 568 | =head1 Installation | ||||||||||||||||||||||||||||
| 569 | |||||||||||||||||||||||||||||
| 570 | This module is written in 100% Pure Perl and is thus easy to read, modify and | ||||||||||||||||||||||||||||
| 571 | install. | ||||||||||||||||||||||||||||
| 572 | |||||||||||||||||||||||||||||
| 573 | Standard Module::Build process for building and installing modules: | ||||||||||||||||||||||||||||
| 574 | |||||||||||||||||||||||||||||
| 575 | perl Build.PL | ||||||||||||||||||||||||||||
| 576 | ./Build | ||||||||||||||||||||||||||||
| 577 | ./Build test | ||||||||||||||||||||||||||||
| 578 | ./Build install | ||||||||||||||||||||||||||||
| 579 | |||||||||||||||||||||||||||||
| 580 | =head1 Author | ||||||||||||||||||||||||||||
| 581 | |||||||||||||||||||||||||||||
| 582 | philiprbrenan@gmail.com | ||||||||||||||||||||||||||||
| 583 | |||||||||||||||||||||||||||||
| 584 | http://www.appaapps.com | ||||||||||||||||||||||||||||
| 585 | |||||||||||||||||||||||||||||
| 586 | =head1 Copyright | ||||||||||||||||||||||||||||
| 587 | |||||||||||||||||||||||||||||
| 588 | Copyright (c) 2016 Philip R Brenan. | ||||||||||||||||||||||||||||
| 589 | |||||||||||||||||||||||||||||
| 590 | This module is free software. It may be used, redistributed and/or modified | ||||||||||||||||||||||||||||
| 591 | under the same terms as Perl itself. | ||||||||||||||||||||||||||||
| 592 | |||||||||||||||||||||||||||||
| 593 | =cut | ||||||||||||||||||||||||||||
| 594 | |||||||||||||||||||||||||||||
| 595 | __DATA__ | ||||||||||||||||||||||||||||