file.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package counter
     6  
     7  import (
     8  	"bytes"
     9  	"errors"
    10  	"fmt"
    11  	"math/rand"
    12  	"os"
    13  	"path"
    14  	"path/filepath"
    15  	"runtime"
    16  	"runtime/debug"
    17  	"sync"
    18  	"sync/atomic"
    19  	"time"
    20  	"unsafe"
    21  
    22  	"golang.org/x/telemetry/internal/mmap"
    23  	"golang.org/x/telemetry/internal/telemetry"
    24  )
    25  
    26  // A file is a counter file.
    27  type file struct {
    28  	// Linked list of all known counters.
    29  	// (Linked list insertion is easy to make lock-free,
    30  	// and we don't want the initial counters incremented
    31  	// by a program to cause significant contention.)
    32  	counters atomic.Pointer[Counter] // head of list
    33  	end      Counter                 // list ends at &end instead of nil
    34  
    35  	mu                 sync.Mutex
    36  	buildInfo          *debug.BuildInfo
    37  	timeBegin, timeEnd time.Time
    38  	err                error
    39  	// current holds the current file mapping, which may change when the file is
    40  	// rotated or extended.
    41  	//
    42  	// current may be read without holding mu, but may be nil.
    43  	//
    44  	// The cleanup logic for file mappings is complicated, because invalidating
    45  	// counter pointers is reentrant: [file.invalidateCounters] may call
    46  	// [file.lookup], which acquires mu. Therefore, writing current must be done
    47  	// as follows:
    48  	//  1. record the previous value of current
    49  	//  2. Store a new value in current
    50  	//  3. unlock mu
    51  	//  4. call invalidateCounters
    52  	//  5. close the previous mapped value from (1)
    53  	// TODO(rfindley): simplify
    54  	current atomic.Pointer[mappedFile]
    55  }
    56  
    57  var defaultFile file
    58  
    59  // register ensures that the counter c is registered with the file.
    60  func (f *file) register(c *Counter) {
    61  	debugPrintf("register %s %p\n", c.Name(), c)
    62  
    63  	// If counter is not registered with file, register it.
    64  	// Doing this lazily avoids init-time work
    65  	// as well as any execution cost at all for counters
    66  	// that are not used in a given program.
    67  	wroteNext := false
    68  	for wroteNext || c.next.Load() == nil {
    69  		head := f.counters.Load()
    70  		next := head
    71  		if next == nil {
    72  			next = &f.end
    73  		}
    74  		debugPrintf("register %s next %p\n", c.Name(), next)
    75  		if !wroteNext {
    76  			if !c.next.CompareAndSwap(nil, next) {
    77  				debugPrintf("register %s cas failed %p\n", c.Name(), c.next.Load())
    78  				continue
    79  			}
    80  			wroteNext = true
    81  		} else {
    82  			c.next.Store(next)
    83  		}
    84  		if f.counters.CompareAndSwap(head, c) {
    85  			debugPrintf("registered %s %p\n", c.Name(), f.counters.Load())
    86  			return
    87  		}
    88  		debugPrintf("register %s cas2 failed %p %p\n", c.Name(), f.counters.Load(), head)
    89  	}
    90  }
    91  
    92  // invalidateCounters marks as invalid all the pointers
    93  // held by f's counters and then refreshes them.
    94  //
    95  // invalidateCounters cannot be called while holding f.mu,
    96  // because a counter refresh may call f.lookup.
    97  func (f *file) invalidateCounters() {
    98  	// Mark every counter as needing to refresh its count pointer.
    99  	if head := f.counters.Load(); head != nil {
   100  		for c := head; c != &f.end; c = c.next.Load() {
   101  			c.invalidate()
   102  		}
   103  		for c := head; c != &f.end; c = c.next.Load() {
   104  			c.refresh()
   105  		}
   106  	}
   107  }
   108  
   109  // lookup looks up the counter with the given name in the file,
   110  // allocating it if needed, and returns a pointer to the atomic.Uint64
   111  // containing the counter data.
   112  // If the file has not been opened yet, lookup returns nil.
   113  func (f *file) lookup(name string) counterPtr {
   114  	current := f.current.Load()
   115  	if current == nil {
   116  		debugPrintf("lookup %s - no mapped file\n", name)
   117  		return counterPtr{}
   118  	}
   119  	ptr := f.newCounter(name)
   120  	if ptr == nil {
   121  		return counterPtr{}
   122  	}
   123  	return counterPtr{current, ptr}
   124  }
   125  
   126  // ErrDisabled is the error returned when telemetry is disabled.
   127  var ErrDisabled = errors.New("counter: disabled as Go telemetry is off")
   128  
   129  var (
   130  	errNoBuildInfo = errors.New("counter: missing build info")
   131  	errCorrupt     = errors.New("counter: corrupt counter file")
   132  )
   133  
   134  // weekEnd returns the day of the week on which uploads occur (and therefore
   135  // counters expire).
   136  //
   137  // Reads the weekends file, creating one if none exists.
   138  func weekEnd() (time.Weekday, error) {
   139  	// If there is no 'weekends' file create it and initialize it
   140  	// to a random day of the week. There is a short interval for
   141  	// a race.
   142  	weekends := filepath.Join(telemetry.Default.LocalDir(), "weekends")
   143  	day := fmt.Sprintf("%d\n", rand.Intn(7))
   144  	if _, err := os.ReadFile(weekends); err != nil {
   145  		if err := os.MkdirAll(telemetry.Default.LocalDir(), 0777); err != nil {
   146  			debugPrintf("%v: could not create telemetry.LocalDir %s", err, telemetry.Default.LocalDir())
   147  			return 0, err
   148  		}
   149  		if err = os.WriteFile(weekends, []byte(day), 0666); err != nil {
   150  			return 0, err
   151  		}
   152  	}
   153  
   154  	// race is over, read the file
   155  	buf, err := os.ReadFile(weekends)
   156  	// There is no reasonable way of recovering from errors
   157  	// so we just fail
   158  	if err != nil {
   159  		return 0, err
   160  	}
   161  	buf = bytes.TrimSpace(buf)
   162  	if len(buf) == 0 {
   163  		return 0, fmt.Errorf("empty weekends file")
   164  	}
   165  	weekend := time.Weekday(buf[0] - '0') // 0 is Sunday
   166  	// paranoia to make sure the value is legal
   167  	weekend %= 7
   168  	if weekend < 0 {
   169  		weekend += 7
   170  	}
   171  	return weekend, nil
   172  }
   173  
   174  // rotate checks to see whether the file f needs to be rotated,
   175  // meaning to start a new counter file with a different date in the name.
   176  // rotate is also used to open the file initially, meaning f.current can be nil.
   177  // In general rotate should be called just once for each file.
   178  // rotate will arrange a timer to call itself again when necessary.
   179  func (f *file) rotate() {
   180  	expiry := f.rotate1()
   181  	if !expiry.IsZero() {
   182  		delay := time.Until(expiry)
   183  		// Some tests set CounterTime to a time in the past, causing delay to be
   184  		// negative. Avoid infinite loops by delaying at least a short interval.
   185  		//
   186  		// TODO(rfindley): instead, just also mock AfterFunc.
   187  		const minDelay = 1 * time.Minute
   188  		if delay < minDelay {
   189  			delay = minDelay
   190  		}
   191  		// TODO(rsc): Does this do the right thing for laptops closing?
   192  		time.AfterFunc(delay, f.rotate)
   193  	}
   194  }
   195  
   196  func nop() {}
   197  
   198  // CounterTime returns the current UTC time.
   199  // Mutable for testing.
   200  var CounterTime = func() time.Time {
   201  	return time.Now().UTC()
   202  }
   203  
   204  // counterSpan returns the current time span for a counter file, as determined
   205  // by [CounterTime] and the [weekEnd].
   206  func counterSpan() (begin, end time.Time, _ error) {
   207  	year, month, day := CounterTime().Date()
   208  	begin = time.Date(year, month, day, 0, 0, 0, 0, time.UTC)
   209  	// files always begin today, but expire on the next day of the week
   210  	// from the 'weekends' file.
   211  	weekend, err := weekEnd()
   212  	if err != nil {
   213  		return time.Time{}, time.Time{}, err
   214  	}
   215  	incr := int(weekend - begin.Weekday())
   216  	if incr <= 0 {
   217  		incr += 7 // ensure that end is later than begin
   218  	}
   219  	end = time.Date(year, month, day+incr, 0, 0, 0, 0, time.UTC)
   220  	return begin, end, nil
   221  }
   222  
   223  // rotate1 rotates the current counter file, returning its expiry, or the zero
   224  // time if rotation failed.
   225  func (f *file) rotate1() time.Time {
   226  	// Cleanup must be performed while unlocked, since invalidateCounters may
   227  	// involve calls to f.lookup.
   228  	var previous *mappedFile // read below while holding the f.mu.
   229  	defer func() {
   230  		// Counters must be invalidated whenever the mapped file changes.
   231  		if next := f.current.Load(); next != previous {
   232  			f.invalidateCounters()
   233  			// Ensure that the previous counter mapped file is closed.
   234  			if previous != nil {
   235  				previous.close() // safe to call multiple times
   236  			}
   237  		}
   238  	}()
   239  
   240  	f.mu.Lock()
   241  	defer f.mu.Unlock()
   242  
   243  	previous = f.current.Load()
   244  
   245  	if f.err != nil {
   246  		return time.Time{} // already in failed state; nothing to do
   247  	}
   248  
   249  	fail := func(err error) {
   250  		debugPrintf("rotate: %v", err)
   251  		f.err = err
   252  		f.current.Store(nil)
   253  	}
   254  
   255  	if mode, _ := telemetry.Default.Mode(); mode == "off" {
   256  		// TODO(rfindley): do we ever want to make ErrDisabled recoverable?
   257  		// Specifically, if f.err is ErrDisabled, should we check again during when
   258  		// rotating?
   259  		fail(ErrDisabled)
   260  		return time.Time{}
   261  	}
   262  
   263  	if f.buildInfo == nil {
   264  		bi, ok := debug.ReadBuildInfo()
   265  		if !ok {
   266  			fail(errNoBuildInfo)
   267  			return time.Time{}
   268  		}
   269  		f.buildInfo = bi
   270  	}
   271  
   272  	begin, end, err := counterSpan()
   273  	if err != nil {
   274  		fail(err)
   275  		return time.Time{}
   276  	}
   277  	if f.timeBegin.Equal(begin) && f.timeEnd.Equal(end) {
   278  		return f.timeEnd // nothing to do
   279  	}
   280  	f.timeBegin, f.timeEnd = begin, end
   281  
   282  	goVers, progPath, progVers := telemetry.ProgramInfo(f.buildInfo)
   283  	meta := fmt.Sprintf("TimeBegin: %s\nTimeEnd: %s\nProgram: %s\nVersion: %s\nGoVersion: %s\nGOOS: %s\nGOARCH: %s\n\n",
   284  		f.timeBegin.Format(time.RFC3339), f.timeEnd.Format(time.RFC3339),
   285  		progPath, progVers, goVers, runtime.GOOS, runtime.GOARCH)
   286  	if len(meta) > maxMetaLen { // should be impossible for our use
   287  		fail(fmt.Errorf("metadata too long"))
   288  		return time.Time{}
   289  	}
   290  
   291  	if progVers != "" {
   292  		progVers = "@" + progVers
   293  	}
   294  	baseName := fmt.Sprintf("%s%s-%s-%s-%s-%s.%s.count",
   295  		path.Base(progPath),
   296  		progVers,
   297  		goVers,
   298  		runtime.GOOS,
   299  		runtime.GOARCH,
   300  		f.timeBegin.Format(time.DateOnly),
   301  		FileVersion,
   302  	)
   303  	dir := telemetry.Default.LocalDir()
   304  	if err := os.MkdirAll(dir, 0777); err != nil {
   305  		fail(fmt.Errorf("making local dir: %v", err))
   306  		return time.Time{}
   307  	}
   308  	name := filepath.Join(dir, baseName)
   309  
   310  	m, err := openMapped(name, meta)
   311  	if err != nil {
   312  		// Mapping failed:
   313  		// If there used to be a mapped file, after cleanup
   314  		// incrementing counters will only change their internal state.
   315  		// (before cleanup the existing mapped file would be updated)
   316  		fail(fmt.Errorf("openMapped: %v", err))
   317  		return time.Time{}
   318  	}
   319  
   320  	debugPrintf("using %v", m.f.Name())
   321  	f.current.Store(m)
   322  	return f.timeEnd
   323  }
   324  
   325  func (f *file) newCounter(name string) *atomic.Uint64 {
   326  	v, cleanup := f.newCounter1(name)
   327  	cleanup()
   328  	return v
   329  }
   330  
   331  func (f *file) newCounter1(name string) (v *atomic.Uint64, cleanup func()) {
   332  	f.mu.Lock()
   333  	defer f.mu.Unlock()
   334  
   335  	current := f.current.Load()
   336  	if current == nil {
   337  		return nil, nop
   338  	}
   339  	debugPrintf("newCounter %s in %s\n", name, current.f.Name())
   340  	if v, _, _, _ := current.lookup(name); v != nil {
   341  		return v, nop
   342  	}
   343  	v, newM, err := current.newCounter(name)
   344  	if err != nil {
   345  		debugPrintf("newCounter %s: %v\n", name, err)
   346  		return nil, nop
   347  	}
   348  
   349  	cleanup = nop
   350  	if newM != nil {
   351  		f.current.Store(newM)
   352  		cleanup = func() {
   353  			f.invalidateCounters()
   354  			current.close()
   355  		}
   356  	}
   357  	return v, cleanup
   358  }
   359  
   360  var (
   361  	openOnce sync.Once
   362  	// rotating reports whether the call to Open had rotate = true.
   363  	//
   364  	// In golang/go#68497, we observed that file rotation can break runtime
   365  	// deadlock detection. To minimize the fix for 1.23, we are splitting the
   366  	// Open API into one version that rotates the counter file, and another that
   367  	// does not. The rotating variable guards against use of both APIs from the
   368  	// same process.
   369  	rotating bool
   370  )
   371  
   372  // Open associates counting with the defaultFile.
   373  // The returned function is for testing only, and should
   374  // be called after all Inc()s are finished, but before
   375  // any reports are generated.
   376  // (Otherwise expired count files will not be deleted on Windows.)
   377  func Open(rotate bool) func() {
   378  	if telemetry.DisabledOnPlatform {
   379  		return func() {}
   380  	}
   381  	close := func() {}
   382  	openOnce.Do(func() {
   383  		rotating = rotate
   384  		if mode, _ := telemetry.Default.Mode(); mode == "off" {
   385  			// Don't open the file when telemetry is off.
   386  			defaultFile.err = ErrDisabled
   387  			// No need to clean up.
   388  			return
   389  		}
   390  		debugPrintf("Open(%v)", rotate)
   391  		if rotate {
   392  			defaultFile.rotate() // calls rotate1 and schedules a rotation
   393  		} else {
   394  			defaultFile.rotate1()
   395  		}
   396  		close = func() {
   397  			// Once this has been called, the defaultFile is no longer usable.
   398  			mf := defaultFile.current.Load()
   399  			if mf == nil {
   400  				// telemetry might have been off
   401  				return
   402  			}
   403  			mf.close()
   404  		}
   405  	})
   406  	if rotating != rotate {
   407  		panic("BUG: Open called with inconsistent values for 'rotate'")
   408  	}
   409  	return close
   410  }
   411  
   412  const (
   413  	FileVersion = "v1"
   414  	hdrPrefix   = "# telemetry/counter file " + FileVersion + "\n"
   415  	recordUnit  = 32
   416  	maxMetaLen  = 512
   417  	numHash     = 512 // 2kB for hash table
   418  	maxNameLen  = 4 * 1024
   419  	limitOff    = 0
   420  	hashOff     = 4
   421  	pageSize    = 16 * 1024
   422  	minFileLen  = 16 * 1024
   423  )
   424  
   425  // A mappedFile is a counter file mmapped into memory.
   426  //
   427  // The file layout for a mappedFile m is as follows:
   428  //
   429  //	offset, byte size:                 description
   430  //	------------------                 -----------
   431  //	0, hdrLen:                         header, containing metadata; see [mappedHeader]
   432  //	hdrLen+limitOff, 4:                uint32 allocation limit (byte offset of the end of counter records)
   433  //	hdrLen+hashOff, 4*numHash:         hash table, stores uint32 heads of a linked list of records, keyed by name hash
   434  //	hdrLen+hashOff+4*numHash to limit: counter records: see record syntax below
   435  //
   436  // The record layout is as follows:
   437  //
   438  //	offset, byte size: description
   439  //	------------------ -----------
   440  //	0, 8:              uint64 counter value
   441  //	8, 12:             uint32 name length
   442  //	12, 16:            uint32 offset of next record in linked list
   443  //	16, name length:   counter name
   444  type mappedFile struct {
   445  	meta      string
   446  	hdrLen    uint32
   447  	zero      [4]byte
   448  	closeOnce sync.Once
   449  	f         *os.File
   450  	mapping   *mmap.Data
   451  }
   452  
   453  // openMapped opens and memory maps a file.
   454  //
   455  // name is the path to the file.
   456  //
   457  // meta is the file metadata, which must match the metadata of the file on disk
   458  // exactly.
   459  //
   460  // existing should be nil the first time this is called for a file,
   461  // and when remapping, should be the previous mappedFile.
   462  func openMapped(name, meta string) (_ *mappedFile, err error) {
   463  	hdr, err := mappedHeader(meta)
   464  	if err != nil {
   465  		return nil, err
   466  	}
   467  
   468  	f, err := os.OpenFile(name, os.O_RDWR|os.O_CREATE, 0666)
   469  	if err != nil {
   470  		return nil, err
   471  	}
   472  	// Note: using local variable m here, not return value,
   473  	// so that return nil, err does not set m = nil and break the code in the defer.
   474  	m := &mappedFile{
   475  		f:    f,
   476  		meta: meta,
   477  	}
   478  
   479  	defer func() {
   480  		if err != nil {
   481  			m.close()
   482  		}
   483  	}()
   484  
   485  	info, err := f.Stat()
   486  	if err != nil {
   487  		return nil, err
   488  	}
   489  
   490  	// Establish file header and initial data area if not already present.
   491  	if info.Size() < minFileLen {
   492  		if _, err := f.WriteAt(hdr, 0); err != nil {
   493  			return nil, err
   494  		}
   495  		// Write zeros at the end of the file to extend it to minFileLen.
   496  		if _, err := f.WriteAt(m.zero[:], int64(minFileLen-len(m.zero))); err != nil {
   497  			return nil, err
   498  		}
   499  		info, err = f.Stat()
   500  		if err != nil {
   501  			return nil, err
   502  		}
   503  		if info.Size() < minFileLen {
   504  			return nil, fmt.Errorf("counter: writing file did not extend it")
   505  		}
   506  	}
   507  
   508  	// Map into memory.
   509  	mapping, err := memmap(f)
   510  	if err != nil {
   511  		return nil, err
   512  	}
   513  	m.mapping = mapping
   514  	if !bytes.HasPrefix(m.mapping.Data, hdr) {
   515  		// TODO(rfindley): we can and should do better here, reading the mapped
   516  		// header length and comparing headers exactly.
   517  		return nil, fmt.Errorf("counter: header mismatch")
   518  	}
   519  	m.hdrLen = uint32(len(hdr))
   520  
   521  	return m, nil
   522  }
   523  
   524  func mappedHeader(meta string) ([]byte, error) {
   525  	if len(meta) > maxMetaLen {
   526  		return nil, fmt.Errorf("counter: metadata too large")
   527  	}
   528  	np := round(len(hdrPrefix), 4)
   529  	n := round(np+4+len(meta), 32)
   530  	hdr := make([]byte, n)
   531  	copy(hdr, hdrPrefix)
   532  	*(*uint32)(unsafe.Pointer(&hdr[np])) = uint32(n)
   533  	copy(hdr[np+4:], meta)
   534  	return hdr, nil
   535  }
   536  
   537  func (m *mappedFile) place(limit uint32, name string) (start, end uint32) {
   538  	if limit == 0 {
   539  		// first record in file
   540  		limit = m.hdrLen + hashOff + 4*numHash
   541  	}
   542  	n := round(uint32(16+len(name)), recordUnit)
   543  	start = round(limit, recordUnit) // should already be rounded but just in case
   544  	// Note: Checking for crossing a page boundary would be
   545  	// start/pageSize != (start+n-1)/pageSize,
   546  	// but we are checking for reaching the page end, so no -1.
   547  	// The page end is reserved for use by extend.
   548  	// See the comment in m.extend.
   549  	if start/pageSize != (start+n)/pageSize {
   550  		// bump start to next page
   551  		start = round(limit, pageSize)
   552  	}
   553  	return start, start + n
   554  }
   555  
   556  var memmap = mmap.Mmap
   557  var munmap = mmap.Munmap
   558  
   559  func (m *mappedFile) close() {
   560  	m.closeOnce.Do(func() {
   561  		if m.mapping != nil {
   562  			munmap(m.mapping)
   563  			m.mapping = nil
   564  		}
   565  		if m.f != nil {
   566  			m.f.Close() // best effort
   567  			m.f = nil
   568  		}
   569  	})
   570  }
   571  
   572  // hash returns the hash code for name.
   573  // The implementation is FNV-1a.
   574  // This hash function is a fixed detail of the file format.
   575  // It cannot be changed without also changing the file format version.
   576  func hash(name string) uint32 {
   577  	const (
   578  		offset32 = 2166136261
   579  		prime32  = 16777619
   580  	)
   581  	h := uint32(offset32)
   582  	for i := 0; i < len(name); i++ {
   583  		c := name[i]
   584  		h = (h ^ uint32(c)) * prime32
   585  	}
   586  	return (h ^ (h >> 16)) % numHash
   587  }
   588  
   589  func (m *mappedFile) load32(off uint32) uint32 {
   590  	if int64(off) >= int64(len(m.mapping.Data)) {
   591  		return 0
   592  	}
   593  	return (*atomic.Uint32)(unsafe.Pointer(&m.mapping.Data[off])).Load()
   594  }
   595  
   596  func (m *mappedFile) cas32(off, old, new uint32) bool {
   597  	if int64(off) >= int64(len(m.mapping.Data)) {
   598  		panic("bad cas32") // return false would probably loop
   599  	}
   600  	return (*atomic.Uint32)(unsafe.Pointer(&m.mapping.Data[off])).CompareAndSwap(old, new)
   601  }
   602  
   603  // entryAt reads a counter record at the given byte offset.
   604  //
   605  // See the documentation for [mappedFile] for a description of the counter record layout.
   606  func (m *mappedFile) entryAt(off uint32) (name []byte, next uint32, v *atomic.Uint64, ok bool) {
   607  	if off < m.hdrLen+hashOff || int64(off)+16 > int64(len(m.mapping.Data)) {
   608  		return nil, 0, nil, false
   609  	}
   610  	nameLen := m.load32(off+8) & 0x00ffffff
   611  	if nameLen == 0 || int64(off)+16+int64(nameLen) > int64(len(m.mapping.Data)) {
   612  		return nil, 0, nil, false
   613  	}
   614  	name = m.mapping.Data[off+16 : off+16+nameLen]
   615  	next = m.load32(off + 12)
   616  	v = (*atomic.Uint64)(unsafe.Pointer(&m.mapping.Data[off]))
   617  	return name, next, v, true
   618  }
   619  
   620  // writeEntryAt writes a new counter record at the given offset.
   621  //
   622  // See the documentation for [mappedFile] for a description of the counter record layout.
   623  //
   624  // writeEntryAt only returns false in the presence of some form of corruption:
   625  // an offset outside the bounds of the record region in the mapped file.
   626  func (m *mappedFile) writeEntryAt(off uint32, name string) (next *atomic.Uint32, v *atomic.Uint64, ok bool) {
   627  	// TODO(rfindley): shouldn't this first condition be off < m.hdrLen+hashOff+4*numHash?
   628  	if off < m.hdrLen+hashOff || int64(off)+16+int64(len(name)) > int64(len(m.mapping.Data)) {
   629  		return nil, nil, false
   630  	}
   631  	copy(m.mapping.Data[off+16:], name)
   632  	atomic.StoreUint32((*uint32)(unsafe.Pointer(&m.mapping.Data[off+8])), uint32(len(name))|0xff000000)
   633  	next = (*atomic.Uint32)(unsafe.Pointer(&m.mapping.Data[off+12]))
   634  	v = (*atomic.Uint64)(unsafe.Pointer(&m.mapping.Data[off]))
   635  	return next, v, true
   636  }
   637  
   638  // lookup searches the mapped file for a counter record with the given name, returning:
   639  //   - v: the mapped counter value
   640  //   - headOff: the offset of the head pointer (see [mappedFile])
   641  //   - head: the value of the head pointer
   642  //   - ok: whether lookup succeeded
   643  func (m *mappedFile) lookup(name string) (v *atomic.Uint64, headOff, head uint32, ok bool) {
   644  	h := hash(name)
   645  	headOff = m.hdrLen + hashOff + h*4
   646  	head = m.load32(headOff)
   647  	off := head
   648  	for off != 0 {
   649  		ename, next, v, ok := m.entryAt(off)
   650  		if !ok {
   651  			return nil, 0, 0, false
   652  		}
   653  		if string(ename) == name {
   654  			return v, headOff, head, true
   655  		}
   656  		off = next
   657  	}
   658  	return nil, headOff, head, true
   659  }
   660  
   661  // newCounter allocates and writes a new counter record with the given name.
   662  //
   663  // If name is already recorded in the file, newCounter returns the existing counter.
   664  func (m *mappedFile) newCounter(name string) (v *atomic.Uint64, m1 *mappedFile, err error) {
   665  	if len(name) > maxNameLen {
   666  		return nil, nil, fmt.Errorf("counter name too long")
   667  	}
   668  	orig := m
   669  	defer func() {
   670  		if m != orig {
   671  			if err != nil {
   672  				m.close()
   673  			} else {
   674  				m1 = m
   675  			}
   676  		}
   677  	}()
   678  
   679  	v, headOff, head, ok := m.lookup(name)
   680  	for tries := 0; !ok; tries++ {
   681  		if tries >= 10 {
   682  			debugFatalf("corrupt: failed to remap after 10 tries")
   683  			return nil, nil, errCorrupt
   684  		}
   685  		// Lookup found an invalid pointer,
   686  		// perhaps because the file has grown larger than the mapping.
   687  		limit := m.load32(m.hdrLen + limitOff)
   688  		if limit, datalen := int64(limit), int64(len(m.mapping.Data)); limit <= datalen {
   689  			// Mapping doesn't need to grow, so lookup found actual corruption,
   690  			// in the form of an entry pointer that exceeds the recorded allocation
   691  			// limit. This should never happen, unless the actual file contents are
   692  			// corrupt.
   693  			debugFatalf("corrupt: limit %d is within mapping length %d", limit, datalen)
   694  			return nil, nil, errCorrupt
   695  		}
   696  		// That the recorded limit is greater than the mapped data indicates that
   697  		// an external process has extended the file. Re-map to pick up this extension.
   698  		newM, err := openMapped(m.f.Name(), m.meta)
   699  		if err != nil {
   700  			return nil, nil, err
   701  		}
   702  		if limit, datalen := int64(limit), int64(len(newM.mapping.Data)); limit > datalen {
   703  			// We've re-mapped, yet limit still exceeds the data length. This
   704  			// indicates that the underlying file was somehow truncated, or the
   705  			// recorded limit is corrupt.
   706  			debugFatalf("corrupt: limit %d exceeds file size %d", limit, datalen)
   707  			return nil, nil, errCorrupt
   708  		}
   709  		// If m != orig, this is at least the second time around the loop
   710  		// trying to open the mapping. Close the previous attempt.
   711  		if m != orig {
   712  			m.close()
   713  		}
   714  		m = newM
   715  		v, headOff, head, ok = m.lookup(name)
   716  	}
   717  	if v != nil {
   718  		return v, nil, nil
   719  	}
   720  
   721  	// Reserve space for new record.
   722  	// We are competing against other programs using the same file,
   723  	// so we use a compare-and-swap on the allocation limit in the header.
   724  	var start, end uint32
   725  	for {
   726  		// Determine where record should end, and grow file if needed.
   727  		limit := m.load32(m.hdrLen + limitOff)
   728  		start, end = m.place(limit, name)
   729  		debugPrintf("place %s at %#x-%#x\n", name, start, end)
   730  		if int64(end) > int64(len(m.mapping.Data)) {
   731  			newM, err := m.extend(end)
   732  			if err != nil {
   733  				return nil, nil, err
   734  			}
   735  			if m != orig {
   736  				m.close()
   737  			}
   738  			m = newM
   739  			continue
   740  		}
   741  
   742  		// Attempt to reserve that space for our record.
   743  		if m.cas32(m.hdrLen+limitOff, limit, end) {
   744  			break
   745  		}
   746  	}
   747  
   748  	// Write record.
   749  	next, v, ok := m.writeEntryAt(start, name)
   750  	if !ok {
   751  		debugFatalf("corrupt: failed to write entry: %#x+%d vs %#x\n", start, len(name), len(m.mapping.Data))
   752  		return nil, nil, errCorrupt // more likely our math is wrong
   753  	}
   754  
   755  	// Link record into hash chain, making sure not to introduce a duplicate.
   756  	// We know name does not appear in the chain starting at head.
   757  	for {
   758  		next.Store(head)
   759  		if m.cas32(headOff, head, start) {
   760  			return v, nil, nil
   761  		}
   762  
   763  		// Check new elements in chain for duplicates.
   764  		old := head
   765  		head = m.load32(headOff)
   766  		for off := head; off != old; {
   767  			ename, enext, v, ok := m.entryAt(off)
   768  			if !ok {
   769  				return nil, nil, errCorrupt
   770  			}
   771  			if string(ename) == name {
   772  				next.Store(^uint32(0)) // mark ours as dead
   773  				return v, nil, nil
   774  			}
   775  			off = enext
   776  		}
   777  	}
   778  }
   779  
   780  func (m *mappedFile) extend(end uint32) (*mappedFile, error) {
   781  	end = round(end, pageSize)
   782  	info, err := m.f.Stat()
   783  	if err != nil {
   784  		return nil, err
   785  	}
   786  	if info.Size() < int64(end) {
   787  		// Note: multiple processes could be calling extend at the same time,
   788  		// but this write only writes the last 4 bytes of the page.
   789  		// The last 4 bytes of the page are reserved for this purpose and hold no data.
   790  		// (In m.place, if a new record would extend to the very end of the page,
   791  		// it is placed in the next page instead.)
   792  		// So it is fine if multiple processes extend at the same time.
   793  		if _, err := m.f.WriteAt(m.zero[:], int64(end)-int64(len(m.zero))); err != nil {
   794  			return nil, err
   795  		}
   796  	}
   797  	newM, err := openMapped(m.f.Name(), m.meta)
   798  	if err != nil {
   799  		return nil, err
   800  	}
   801  	if int64(len(newM.mapping.Data)) < int64(end) {
   802  		// File system or logic bug: new file is somehow not extended.
   803  		// See go.dev/issue/68311, where this appears to have been happening.
   804  		newM.close()
   805  		return nil, errCorrupt
   806  	}
   807  	return newM, err
   808  }
   809  
   810  // round returns x rounded up to the next multiple of unit,
   811  // which must be a power of two.
   812  func round[T int | uint32](x T, unit T) T {
   813  	return (x + unit - 1) &^ (unit - 1)
   814  }
   815
View as plain text