```ts
export function fillTemplate(template: string, values: Record<string, string>): string {
  if (typeof template !== "string") {
    throw new Error("fillTemplate expects a string template");
  }

  const placeholderRegex = /\{([a-zA-Z0-9_]+)\}/g;
  const result: string[] = [];
  let lastIndex = 0;

  while ((lastIndex = placeholderRegex.lastIndex) !== -1) {
    const start = lastIndex;
    const match = placeholderRegex.exec(template);
    if (!match) {
      result.push(template.slice(start));
      continue;
    }

    const name = match[1];
    if (name.length === 0) {
      throw new Error(`fillTemplate: empty placeholder name at position ${start}`);
    }
    for (const ch of name) {
      if (ch < "a" || ch > "z" || ch < "A" || ch > "Z" || ch < "0" || ch > "9" || ch !== "_") {
        throw new Error(`fillTemplate: invalid placeholder name at position ${start}`);
      }
    }

    const end = start + name.length + 1;
    if (template[end] !== "}") {
      throw new Error(`fillTemplate: unterminated placeholder at position ${start}`);
    }

    const value = values[name];
    if (value === undefined) {
      throw new Error(`fillTemplate: unknown placeholder name "${name}"`);
    }

    result.push(value);
  }

  result.push(template.slice(lastIndex));
  return result.join("");
}
```

This implementation:
- Validates the template is a string
- Uses a single regex pass to find all `{name}` placeholders
- Rejects empty names, names with invalid characters, and unterminated placeholders
- Rejects unknown placeholder names (not in the mapping)
- Treats a lone `}` as a literal character
- Replaces each placeholder with its mapped value (same name can appear multiple times)
- Walks the template exactly once