hivemind

package
v0.0.0-...-6175fdf Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 9, 2024 License: MIT Imports: 16 Imported by: 0

Documentation

Overview

Package hivemind implements the TreadMarks API.

This file contains the API and the top level handlers for the HiveMind DSM

Package hivemind implements the TreadMarks API.

This file contains the implementation of the IntervalRecord

Package hivemind implements the TreadMarks API.

This file contains the implementation of the Barrier and Lock managers

Package hivemind implements the TreadMarks API.

This file contains the implementation of the PageArray and PageEntry objects

Package hivemind implements the TreadMarks API.

This file contains the implementation of the processor array and processor entry objects

Package hivemind implements the TreadMarks API.

This file contains the implementation of the vector timestamp

Package hivemind implements the TreadMarks API.

This file contains the implementation of the WriteNoticeRecord

Index

Constants

View Source 
const (
	LOCKREQ = 10 /* Lock Acquirer 	  -> 	Lock Holder      */
	LOCKRSP = 11 /* Lock Holder 	  -> 	Lock Acquirer    */
	DIFFREQ = 20 /* PagefaultHandler  -> 	Writers 		 */
	DIFFRSP = 21 /* Writers 		  -> 	PageFaultHandler */
	PAGEREQ = 30 /* PageFaultHandler  -> 	Page Owner       */
	PAGERSP = 31 /* Page Owner 		  -> 	PageFaultHandler */
	BARRREQ = 40 /* Barrier Client 	  -> 	Barrier Manager  */
	BARRRSP = 41 /* Barrier Manager   -> 	Barrier Client   */

)

List of Message IDs sent between the HiveMind drones (i.e. nodes)

Variables

View Source 
var LogChan chan string = make(chan string, 100)

Functions

func ApplyDiff 

func ApplyDiff(page []byte, diff Diff)

ApplyDiff updates the page with the diffs

func BarrierCall 

func BarrierCall(caller string)

func DumpLog 

func DumpLog()

func InitManager 

func InitManager(initList []string, Tx chan ipc.IpcMessage)

func VCToArray 

func VCToArray(vc *Vclock) []uint

VCToArray Returns internal clockmap uint slice

Types

type BarrierRequest 

type BarrierRequest struct {
	BarrierID uint8
	Vc        Vclock
	Intervals []IntervalRec
}

type BarrierResponse 

type BarrierResponse struct {
	Intervals []IntervalRec
	Vc        Vclock
}

type Diff 

type Diff []DiffChar

Diff is the data structure that describes the diff between two pages

func GetDiff 

func GetDiff(old, new []byte) Diff

GetDiff generates the run-length encode diff between two pages

type DiffChar 

type DiffChar struct {
	Offset int  // offset into the page
	Char   byte // new value at the offset
}

DiffChar keeps track of one character difference in a page

type DiffInfo 

type DiffInfo struct {
	Diff     Diff
	ProcID   uint8
	Interval uint
	PageID   int
}

DiffInfo struct for communicating diffs between drones

type DiffRequest 

type DiffRequest struct {
	Page    int16
	VcStart Vclock
	VcEnd   Vclock
}

type DiffResponse 

type DiffResponse struct {
	Page int16
	WN   []WriteNotice
}

type HM 

type HM struct {
	VC Vclock // local vector clock
	// contains filtered or unexported fields
}

HM encapsulates the entire HiveMind DSM data

func NewHiveMind 

func NewHiveMind(pid, nrProc, nrBarriers, nrLocks uint8, nrPages, pageSize int, ipcType string) *HM

NewHiveMind creates a new instance of the HM struct and initializes data structures

func (*HM) Barrier 

func (hm *HM) Barrier(b uint8)

Barrier blocks the calling process until all other processes arrive at the barrier

func (*HM) ConnectToPeers 

func (hm *HM) ConnectToPeers(ids []uint8, ips []string)

ConnectToPeers is a test function to work with tipc for uniting testing hivemind. Will be replaced by ipc later

func (*HM) CreateInterval 

func (hm *HM) CreateInterval()

CreateInterval creates a new interval record for the current interval; and for all the pages modified during the interval it creates write notice records.

func (*HM) Exit 

func (hm *HM) Exit()

Exit is called to shutdown the HiveMind DSM.

func (*HM) Free 

func (hm *HM) Free(addr int) error

Free a previously allocated block of memory.

func (*HM) GetNProcs 

func (hm *HM) GetNProcs() uint8

GetNProcs gets the number of processors configured for this DSM

func (*HM) GetProcID 

func (hm *HM) GetProcID() uint8

GetProcID gets the processor ID of this process

func (*HM) IncorporateIntervals 

func (hm *HM) IncorporateIntervals(intervals []IntervalRec)

IncorporateIntervals is called by the lock acquirer to incorporate the information received in the reply in its own data structures. Notice that the system creates a diff for writable pages for which a write notice was received. This is important to allow the system to distinguish the modifications made by concurrent writers to the page. The status of the pages for which write notices were received in the reply is set to no-access. When the acquirer tries to access one of the invalidated pages the system invokes the PageFaultHandler

func (*HM) LockAcquire 

func (hm *HM) LockAcquire(lock uint8)

LockAcquire blocks the calling process until it acquires the specified lock

func (*HM) LockRelease 

func (hm *HM) LockRelease(lock uint8)

LockRelease releases the specified lock

func (*HM) Log 

func (hm *HM) Log(f string, a ...interface{})

Log is called by all of the log functions and formats the messages and puts on the global Log channel

func (*HM) LogDebug 

func (hm *HM) LogDebug(f string, a ...interface{})

LogDebug used to log verbose debug info useful for debuggung the system

func (*HM) LogError 

func (hm *HM) LogError(f string, a ...interface{})

LogError used to log any error messages

func (*HM) LogInfo 

func (hm *HM) LogInfo(f string, a ...interface{})

LogInfo used to log any info messages

func (*HM) LogMsg 

func (hm *HM) LogMsg(f string, a ...interface{})

LogMsg used to log messages sent to and received from IPC layer

func (*HM) Malloc 

func (hm *HM) Malloc(size int) (int, error)

Malloc a block of free memory and returns the start of that block

func (*HM) Read 

func (hm *HM) Read(addr int) (val byte, err error)

Read a single byte at the specified address

func (*HM) ReadFloat 

func (hm *HM) ReadFloat(addr int) (val float64, err error)

ReadFloat reads a single float64 at the specified address

func (*HM) ReadN 

func (hm *HM) ReadN(addr int, len int) (val []byte, err error)

ReadN an array of bytes at the specified address

func (*HM) SetDebug 

func (hm *HM) SetDebug(level int)

SetDebug sets the debug message level. Lower levels are included in higher levels 0 - disable all output 1 - Enable Error messages 2 - Enable Info messages 3 - Enables IPC message trace 4 - Enable Debug messages

func (*HM) Startup 

func (hm *HM) Startup(gvec string)

Startup starts the HiveMind DSM on all processors. It should be the first call

func (*HM) StartupTipc 

func (hm *HM) StartupTipc(port int, gvec string)

StartupTipc starts hivemind with test ipc library for unit testing

func (*HM) Write 

func (hm *HM) Write(addr int, val byte) error

Write a byte at the specified address

func (*HM) WriteFloat 

func (hm *HM) WriteFloat(addr int, val float64) error

WriteFloat writes a float at the specified address

func (*HM) WriteN 

func (hm *HM) WriteN(addr int, val []byte) error

WriteN an array of bytes at the specified address

type HiveMind 

type HiveMind interface {
	// Allocates a block of free memory and returns the start of that block
	// Can return the following errors:
	// - InsufficientMemory
	Malloc(size int) (int, error)

	// Frees a previously allocated block of memory.
	// Can return the following errors:
	// - InvalidAddress
	// -
	Free(addr int) error

	// Starts the HiveMind DSM on all processors. It should be the first call
	Startup()

	// Exit is called to shutdown the HiveMind DSM.
	Exit()

	// Barrier blocks the calling process until all other processes arrive at the barrier
	Barrier(b uint8)

	// LockAcquire blocks the calling process until it acquires the specified lock
	LockAcquire(lock uint8)

	// LockRelease releases the specified lock
	LockRelease(lock uint8)

	// GetNProcs gets the number of processors configured for this DSM
	GetNProcs() uint8

	// GetProcID gets the processor ID of this process
	GetProcID() uint8

	// Read a single byte at the specified address or Read array of bytes
	// Can return the following errors:
	// -
	Read(addr int) (byte, error)
	ReadN(addr int, len int) ([]byte, error)
	ReadFloat(addr int) (float64, error)

	// Write a byte at address or write an array of bytes starting at address
	// Can return the following errors:
	// -
	Write(addr int, val byte) error
	WriteN(addr int, data []byte) error
	WriteFloat(addr, val float64) error
}

HiveMind interface describes the entire HiveMind DSM interface

type IntervalRec 

type IntervalRec struct {
	ProcID uint8
	Vc     Vclock
	Pages  []int
}

IntervalRec is a slightly different version of the IntervalRecord It is used for the messaging and does not contain list of WriteNotices. Instead it contains just the list of modified pages as described in Costa

type IntervalRecord 

type IntervalRecord struct {
	ProcID       uint8          // id of process which created the interval
	Vc           *Vclock        // vector time of creator
	WriteNotices []*WriteNotice // list of write notice records for this interval.
}

IntervalRecord describes the interval

func NewIntervalRecord 

func NewIntervalRecord(pid uint8, vc *Vclock) *IntervalRecord

NewIntervalRecord is constructor for an interval record

func (*IntervalRecord) AddWN 

func (i *IntervalRecord) AddWN(wn *WriteNotice)

AddWN adds the WriteNotice to the record

func (*IntervalRecord) DelWN 

func (i *IntervalRecord) DelWN(wn *WriteNotice)

DelWN deletes the WriteNotice from the record

func (*IntervalRecord) GetID 

func (i *IntervalRecord) GetID() uint8

GetID gets the procID of the record

func (*IntervalRecord) GetTS 

func (i *IntervalRecord) GetTS() *Vclock

GetTS gets the vector timestamp

func (*IntervalRecord) GetWN 

func (i *IntervalRecord) GetWN() []*WriteNotice

GetWN gets the list Write Notice pointers in the interval

func (IntervalRecord) String 

func (i IntervalRecord) String() string

type IntervalRecordIf 

type IntervalRecordIf interface {
	//GetID gets the procID of the record
	GetID() uint8

	// GetTS gets the vector timestamp
	GetTS() Vclock

	//GetWN gets the list Write Notice pointers in the interval
	GetWN() []*WriteNotice

	//AddWN adds the WriteNotice to the record
	AddWN(wn *WriteNotice)

	//DelWN deletes the WriteNotice from the record
	DelWN(wn *WriteNotice)
}

IntervalRecordIf defines the interface for InterfaceRecord types

type Lock 

type Lock struct {
	// contains filtered or unexported fields
}

Lock holds the state of each lock in the system

type LockAcquireRequest 

type LockAcquireRequest struct {
	AcqID  uint8 // ID of the Acquirer since this message is forwarded
	LockID uint8
	Vc     Vclock
}

Define the list of structures used for Request/Response handlers

type LockAcquireResponse 

type LockAcquireResponse struct {
	LockID    uint8
	Vc        Vclock
	Intervals []IntervalRec
}

type MD 

type MD struct {
	// contains filtered or unexported fields
}

func (*MD) GetPID 

func (md *MD) GetPID() int

type ManaStruct 

type ManaStruct struct {
	Txchan chan ipc.IpcMessage
	// contains filtered or unexported fields
}

when all of tracker = curPhase, we know all drones have reached barrier. then we simply flip curPhase

func (*ManaStruct) Broadcast 

func (ms *ManaStruct) Broadcast()

all drones have reached barrier

func (*ManaStruct) Init 

func (ms *ManaStruct) Init(keylist []string, himpt *HM)

func (*ManaStruct) SetBar 

func (ms *ManaStruct) SetBar(drone string, message BarrierRequest)

type Manager 

type Manager interface {
	// contains filtered or unexported methods
}

Manager manages the DSM processes

type PageArray 

type PageArray struct {
	// contains filtered or unexported fields
}

PageArray is an array of PageEntries -- one for each processor

func NewPageArray 

func NewPageArray(nrPages int, pageSize int, procId, nrProc uint8) *PageArray

NewPageArray creates a new instance of the page array

func (*PageArray) GetPageAddress 

func (pga *PageArray) GetPageAddress(page int) int

func (*PageArray) GetPageEntry 

func (pga *PageArray) GetPageEntry(page int) *PageEntry

func (*PageArray) GetPageSize 

func (pga *PageArray) GetPageSize() int

type PageEntry 

type PageEntry struct {
	// contains filtered or unexported fields
}

PageEntry maintains the stats of shared page in the DSM

func NewPageEntry 

func NewPageEntry(pid uint8, page int, nrProc uint8) *PageEntry

Page Entry Methods

func (*PageEntry) AddCopySet 

func (pe *PageEntry) AddCopySet(proc uint8)

func (*PageEntry) AddWN 

func (pe *PageEntry) AddWN(proc uint8, wn *WriteNotice)

func (*PageEntry) DelTwin 

func (pe *PageEntry) DelTwin()

func (*PageEntry) DumpWriteNotices 

func (pe *PageEntry) DumpWriteNotices() string

func (*PageEntry) GetCopySet 

func (pe *PageEntry) GetCopySet() []uint8

func (*PageEntry) GetDiffRange 

func (pe *PageEntry) GetDiffRange(proc uint8) (start *Vclock, end *Vclock)

func (*PageEntry) GetManager 

func (pe *PageEntry) GetManager() uint8

func (*PageEntry) GetPageID 

func (pe *PageEntry) GetPageID() int

func (*PageEntry) GetPageStatus 

func (pe *PageEntry) GetPageStatus() shm.Prot

func (*PageEntry) GetTwin 

func (pe *PageEntry) GetTwin() []byte

func (*PageEntry) HasCopy 

func (pe *PageEntry) HasCopy() bool

func (*PageEntry) SetHasCopy 

func (pe *PageEntry) SetHasCopy(h bool)

func (*PageEntry) SetManager 

func (pe *PageEntry) SetManager(m uint8)

func (*PageEntry) SetPageStatus 

func (pe *PageEntry) SetPageStatus(prot shm.Prot)

func (*PageEntry) SetTwin 

func (pe *PageEntry) SetTwin(twin []byte)

type PageRequest 

type PageRequest struct {
	Page int16
}

type PageResponse 

type PageResponse struct {
	Page    int16
	Data    []byte
	CopySet []uint8
}

type ProcArray 

type ProcArray struct {
	// contains filtered or unexported fields
}

ProcArray maintains a list of interval records for each processor

func NewProcArray 

func NewProcArray(nrProc uint8) *ProcArray

NewProcArray creates a new instance of the procArray

func (*ProcArray) Dump 

func (pa *ProcArray) Dump() string

Dump returns the processor contents as a string

func (*ProcArray) GetLastRecord 

func (pa *ProcArray) GetLastRecord(p uint8) *IntervalRecord

GetLastRecord gets the latest interval record for a processor

func (*ProcArray) GetLatestLocalTimestamp 

func (pa *ProcArray) GetLatestLocalTimestamp(pid uint8) *Vclock

GetLatestLocalTimestamp gets the latest local timestamp known for a specific processor

func (*ProcArray) GetMissingIntervals 

func (pa *ProcArray) GetMissingIntervals(vc *Vclock) []IntervalRec

GetMissingIntervals gets the intervals on all processors not covered by TS

func (*ProcArray) GetProcMissingIntervals 

func (pa *ProcArray) GetProcMissingIntervals(pid uint8, vc *Vclock) []IntervalRec

GetProcMissingIntervals gets the intervals on a processor that is not covered by TS

func (*ProcArray) InsertInterval 

func (pa *ProcArray) InsertInterval(pid uint8, interval *IntervalRecord)

InsertInterval inserts an interval to the end of the processor list

func (*ProcArray) InsertIntervalRec 

func (pa *ProcArray) InsertIntervalRec(hm *HM, interval IntervalRec) *IntervalRecord

InsertIntervalRec inserts an new IntervalRecord from a IntervalRec. It also creates new writes notices for each of the pages in the Interval pages. The WN are added to the new interval record and also added to the page array. The Interval Record is then appended to the procArray

type Vclock 

type Vclock struct {
	ClockMap []uint
}

Vclock Struct which includes the map that keeps track of intervals

func ArrayToVC 

func ArrayToVC(arr []uint) *Vclock

ArrayToVC Creates a new vc from an uint slice

func NewVectorClock 

func NewVectorClock(nrProc uint8) *Vclock

Get new vector clock that does not contain any values

func (*Vclock) Compare 

func (vc *Vclock) Compare(vc2 *Vclock) []int

Compare Returns a slice of ids which have interval values less than the current vector clock or are not present in the vector clock being compared to but present in the current vector clock Implementation may change

func (*Vclock) Copy 

func (vc *Vclock) Copy() *Vclock

Copy Copies contents of a vector clock into a new vector clock struct

func (*Vclock) Covers 

func (vc *Vclock) Covers(vc2 *Vclock) bool

Covers checks the VC covers another VC according to the covered definition described in Keleher.

func (*Vclock) GetInterval 

func (vc *Vclock) GetInterval(id uint8) (uint, error)

GetInterval Gets the interval for the given id

func (*Vclock) Increment 

func (vc *Vclock) Increment(id uint8) (uint, error)

Increment Increments value given by id and returns the incremented value

func (*Vclock) IsIdentical 

func (vc *Vclock) IsIdentical(vc2 *Vclock) bool

IsIdentical Checks if two vector clocks are identical, i.e. they have the same value for all processes

func (*Vclock) Merge 

func (vc *Vclock) Merge(vc2 *Vclock) *Vclock

Merge Merges two vector clocks together taking the pairwise between two intervals with the same id

func (*Vclock) Min 

func (vc *Vclock) Min(vc2 *Vclock) *Vclock

func (Vclock) String 

func (vc Vclock) String() string

func (*Vclock) Update 

func (vc *Vclock) Update(id uint8, time uint)

Updates the vector clock, if the clock does not contain the given id then it creates a new entry for that id

type WriteNotice 

type WriteNotice struct {
	ProcID uint8   // Creator of this Write Notice
	Diff   *Diff   // pointer to diff
	Vc     *Vclock // pointer to the vector time when created
	PageID int     // number of this page
}

WriteNotice describes modifications to a page. Instead of including a link to the interval record we just put the timestamp and procID. It simplifies the messaging since we can use this structure in the message requests/responses

func NewWriteNotice 

func NewWriteNotice(page int, interval *IntervalRecord) *WriteNotice

NewWriteNotice creates a new Write Notice record using the parameters from the interval. The write notice is added to Page Array and to the Interval

func (*WriteNotice) EmptyDiff 

func (wn *WriteNotice) EmptyDiff() bool

SetDiff sets the diff in this record

func (*WriteNotice) GetDiff 

func (wn *WriteNotice) GetDiff() *Diff

GetDiff gets the pointer to the run-length encode page diff

func (*WriteNotice) GetPageID 

func (wn *WriteNotice) GetPageID() int

GetPageID gets the pageID of the record

func (*WriteNotice) GetTS 

func (wn *WriteNotice) GetTS() *Vclock

GetInterval gets the interval record

func (*WriteNotice) SetDiff 

func (wn *WriteNotice) SetDiff(diff *Diff)

SetDiff sets the diff in this record

func (WriteNotice) String 

func (wn WriteNotice) String() string

type WriteNoticeIf 

type WriteNoticeIf interface {
	//GetInterval gets the interval record
	GetInterval() *IntervalRecord

	// GetDiff gets the pointer to the run-length encode page diff
	GetDiff() *Diff

	// SetDiff sets the diff in this record
	SetDiff(diff *Diff)

	// GetPageID gets the pageID of the record
	GetPageID() int
}

WriteNoticeIf defines methods supported by write notice records

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.